{"id":375,"date":"2025-06-26T21:55:28","date_gmt":"2025-06-26T16:25:28","guid":{"rendered":"https:\/\/codeanddebug.in\/blog\/?p=375"},"modified":"2025-06-26T21:55:30","modified_gmt":"2025-06-26T16:25:30","slug":"two-sum-leetcode-1","status":"publish","type":"post","link":"https:\/\/codeanddebug.in\/blog\/two-sum-leetcode-1\/","title":{"rendered":"Two Sum | Leetcode 1 | Explained with Images"},"content":{"rendered":"\n<p>Given an array of integers&nbsp;<code>nums<\/code>&nbsp;and an integer&nbsp;<code>target<\/code>, return&nbsp;<em>indices of the two numbers such that they add up to&nbsp;<code>target<\/code><\/em>.<\/p>\n\n\n\n<p>You may assume that each input would have&nbsp;<strong><em>exactly<\/em>&nbsp;one solution<\/strong>, and you may not use the&nbsp;<em>same<\/em>&nbsp;element twice.<\/p>\n\n\n\n<p>You can return the answer in any order.<\/p>\n\n\n\n<p>Here&#8217;s the [<strong><a href=\"https:\/\/leetcode.com\/problems\/two-sum\/description\/\" target=\"_blank\" rel=\"noreferrer noopener\"><mark style=\"background-color:rgba(0, 0, 0, 0)\" class=\"has-inline-color has-vivid-purple-color\"><span style=\"text-decoration: underline;\">Problem Link<\/span><\/mark><\/a><\/strong>] to begin with.<\/p>\n\n\n<div style=\"max-width: -moz-fit-content; \" class=\"wp-block-ub-table-of-contents-block ub_table-of-contents ub_table-of-contents-collapsed\" id=\"ub_table-of-contents-7672e0a6-8eb6-4a70-8d80-be762f52a968\" data-linktodivider=\"false\" data-showtext=\"show\" data-hidetext=\"hide\" data-scrolltype=\"auto\" data-enablesmoothscroll=\"true\" data-initiallyhideonmobile=\"false\" data-initiallyshow=\"false\"><div class=\"ub_table-of-contents-header-container\" style=\"\">\n\t\t\t<div class=\"ub_table-of-contents-header\" style=\"text-align: left; \">\n\t\t\t\t<div class=\"ub_table-of-contents-title\">Contents:<\/div>\n\t\t\t\t<div class=\"ub_table-of-contents-header-toggle\">\n\t\t\t<div class=\"ub_table-of-contents-toggle\" style=\"\">\n\t\t\t\u00a0[<a class=\"ub_table-of-contents-toggle-link\" href=\"#\" style=\"\">show<\/a>]\n\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t<\/div>\n\t\t<\/div><div class=\"ub_table-of-contents-extra-container\" style=\"\">\n\t\t\t<div class=\"ub_table-of-contents-container ub_table-of-contents-1-column ub-hide\">\n\t\t\t\t<ul style=\"\"><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/two-sum-leetcode-1\/#0-brute-force-solution\" style=\"\">BRUTE FORCE SOLUTION<\/a><ul><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/two-sum-leetcode-1\/#1-1-problem-statement-\" style=\"\">1. Problem Statement<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/two-sum-leetcode-1\/#2-2-intuition-and-approach-\" style=\"\">2. Intuition and Approach<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/two-sum-leetcode-1\/#3-3-code-\" style=\"\">3. Code<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/two-sum-leetcode-1\/#4-4-dry-run-\" style=\"\">4. Dry Run<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/two-sum-leetcode-1\/#5-5-edge-cases-\" style=\"\">5. Edge Cases<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/two-sum-leetcode-1\/#6-6-time-and-space-complexity-\" style=\"\">6. Time and Space Complexity<\/a><\/li><\/ul><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/two-sum-leetcode-1\/#7-optimal-solution\" style=\"\">OPTIMAL SOLUTION<\/a><ul><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/two-sum-leetcode-1\/#8-1-problem-statement-\" style=\"\">1. Problem Statement<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/two-sum-leetcode-1\/#9-2-intuition-and-approach-\" style=\"\">2. Intuition and Approach<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/two-sum-leetcode-1\/#10-3-code-\" style=\"\">3. Code<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/two-sum-leetcode-1\/#11-4-dry-run-\" style=\"\">4. Dry Run<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/two-sum-leetcode-1\/#12-5-edge-cases-\" style=\"\">5. Edge Cases<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/two-sum-leetcode-1\/#13-6-time-and-space-complexity-\" style=\"\">6. Time and Space Complexity<\/a><\/li><\/ul><\/li><\/ul>\n\t\t\t<\/div>\n\t\t<\/div><\/div>\n\n\n<p><strong>Example 1:<\/strong><br><strong>Input: <\/strong>nums = [2,7,11,15], target = 9<br><strong>Output:<\/strong> [0,1]<br><strong>Explanation:<\/strong> Because nums[0] + nums[1] == 9, we return [0, 1].<\/p>\n\n\n\n<p><strong>Example 2:<\/strong><br><strong>Input:<\/strong> nums = [3,2,4], target = 6<br><strong>Output:<\/strong> [1,2]<\/p>\n\n\n\n<p><strong>Example 3:<\/strong><br><strong>Input:<\/strong> nums = [3,3], target = 6<br><strong>Output:<\/strong> [0,1]<\/p>\n\n\n\n<p><strong>Constraints:<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>2 &lt;= nums.length &lt;= 10<sup>4<\/sup><\/li>\n\n\n\n<li>-10<sup>9<\/sup> &lt;= nums[i] &lt;= 10<sup>9<\/sup><\/li>\n\n\n\n<li>-10<sup>9<\/sup> &lt;= target &lt;= 10<sup>9<\/sup><\/li>\n<\/ul>\n\n\n\n<p><strong>Only one valid answer exists.<\/strong><\/p>\n\n\n<div style=\"max-width: -moz-fit-content; \" class=\"wp-block-ub-table-of-contents-block ub_table-of-contents ub_table-of-contents-collapsed\" id=\"ub_table-of-contents-89e19417-cbc0-4d33-ad6e-d9b6075495e4\" data-linktodivider=\"false\" data-showtext=\"show\" data-hidetext=\"hide\" data-scrolltype=\"auto\" data-enablesmoothscroll=\"true\" data-initiallyhideonmobile=\"false\" data-initiallyshow=\"false\"><div class=\"ub_table-of-contents-header-container\" style=\"\">\n\t\t\t<div class=\"ub_table-of-contents-header\" style=\"text-align: left; \">\n\t\t\t\t<div class=\"ub_table-of-contents-title\">Contents:<\/div>\n\t\t\t\t<div class=\"ub_table-of-contents-header-toggle\">\n\t\t\t<div class=\"ub_table-of-contents-toggle\" style=\"\">\n\t\t\t\u00a0[<a class=\"ub_table-of-contents-toggle-link\" href=\"#\" style=\"\">show<\/a>]\n\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t<\/div>\n\t\t<\/div><div class=\"ub_table-of-contents-extra-container\" style=\"\">\n\t\t\t<div class=\"ub_table-of-contents-container ub_table-of-contents-1-column ub-hide\">\n\t\t\t\t<ul style=\"\"><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/two-sum-leetcode-1\/#0-brute-force-solution\" style=\"\">BRUTE FORCE SOLUTION<\/a><ul><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/two-sum-leetcode-1\/#1-1-problem-statement-\" style=\"\">1. Problem Statement<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/two-sum-leetcode-1\/#2-2-intuition-and-approach-\" style=\"\">2. Intuition and Approach<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/two-sum-leetcode-1\/#3-3-code-\" style=\"\">3. Code<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/two-sum-leetcode-1\/#4-\" style=\"\"><\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/two-sum-leetcode-1\/#5-4-dry-run-\" style=\"\">4. Dry Run<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/two-sum-leetcode-1\/#6-\" style=\"\"><\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/two-sum-leetcode-1\/#7-5-edge-cases-\" style=\"\">5. Edge Cases<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/two-sum-leetcode-1\/#8-6-time-and-space-complexity-\" style=\"\">6. Time and Space Complexity<\/a><\/li><\/ul><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/two-sum-leetcode-1\/#9-optimal-solution\" style=\"\">OPTIMAL SOLUTION<\/a><ul><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/two-sum-leetcode-1\/#10-1-problem-statement-\" style=\"\">1. Problem Statement<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/two-sum-leetcode-1\/#11-2-intuition-and-approach-\" style=\"\">2. Intuition and Approach<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/two-sum-leetcode-1\/#12-3-code-\" style=\"\">3. Code<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/two-sum-leetcode-1\/#13-\" style=\"\"><\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/two-sum-leetcode-1\/#14-4-dry-run-\" style=\"\">4. Dry Run<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/two-sum-leetcode-1\/#15-5-edge-cases-\" style=\"\">5. Edge Cases<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/two-sum-leetcode-1\/#16-6-time-and-space-complexity-\" style=\"\">6. Time and Space Complexity<\/a><\/li><\/ul><\/li><\/ul>\n\t\t\t<\/div>\n\t\t<\/div><\/div>\n\n\n<h2 class=\"wp-block-heading\" id=\"0-brute-force-solution\">BRUTE FORCE SOLUTION<\/h2>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"1-1-problem-statement-\"><strong>1. Problem Statement<\/strong><\/h3>\n\n\n\n<p>The task is to find two numbers in an array nums such that they add up to a specific target target. The function should return the indices of these two numbers. It&#8217;s guaranteed that exactly one solution exists, and you may not use the same element twice.<\/p>\n\n\n\n<p><strong>Input:<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>nums: A list of integers.<\/li>\n\n\n\n<li>target: An integer representing the target sum.<\/li>\n<\/ul>\n\n\n\n<p><strong>Output:<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>A list containing two integers, which are the indices of the two numbers in nums that add up to target.<\/li>\n<\/ul>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"2-2-intuition-and-approach-\"><strong>2. Intuition and Approach<\/strong><\/h3>\n\n\n\n<p>The provided code implements a <strong>brute-force approach<\/strong> to solve the problem:<\/p>\n\n\n\n<ol class=\"wp-block-list\">\n<li><strong>Nested Loops:<\/strong> Iterate over each element in nums using two nested loops.<\/li>\n\n\n\n<li><strong>Sum Check:<\/strong> For each pair of elements (nums[i], nums[j]), check if their sum equals the target.<\/li>\n\n\n\n<li><strong>Return Indices:<\/strong> If a matching pair is found, return their indices [i, j] immediately.<\/li>\n<\/ol>\n\n\n\n<p>This method checks all possible pairs in the array until it finds the pair that sums up to the target.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"3-3-code-\"><strong>3. Code<\/strong><\/h3>\n\n\n\n<div class=\"wp-block-kevinbatdorf-code-block-pro\" data-code-block-pro-font-family=\"Code-Pro-JetBrains-Mono\" style=\"font-size:.875rem;font-family:Code-Pro-JetBrains-Mono,ui-monospace,SFMono-Regular,Menlo,Monaco,Consolas,monospace;line-height:1.25rem;--cbp-tab-width:2;tab-size:var(--cbp-tab-width, 2)\"><span style=\"display:block;padding:16px 0 0 16px;margin-bottom:-1px;width:100%;text-align:left;background-color:#1E1E1E\"><svg xmlns=\"http:\/\/www.w3.org\/2000\/svg\" width=\"54\" height=\"14\" viewBox=\"0 0 54 14\"><g fill=\"none\" fill-rule=\"evenodd\" transform=\"translate(1 1)\"><circle cx=\"6\" cy=\"6\" r=\"6\" fill=\"#FF5F56\" stroke=\"#E0443E\" stroke-width=\".5\"><\/circle><circle cx=\"26\" cy=\"6\" r=\"6\" fill=\"#FFBD2E\" stroke=\"#DEA123\" stroke-width=\".5\"><\/circle><circle cx=\"46\" cy=\"6\" r=\"6\" fill=\"#27C93F\" stroke=\"#1AAB29\" stroke-width=\".5\"><\/circle><\/g><\/svg><\/span><span role=\"button\" tabindex=\"0\" data-code=\"class Solution:\n    def twoSum(self, nums: List[int], target: int) -&gt; List[int]:\n        n = len(nums)\n        for i in range(0, n):\n            for j in range(i + 1, n):\n                if nums[i] + nums[j] == target:\n                    return [i, j]\" style=\"color:#D4D4D4;display:none\" aria-label=\"Copy\" class=\"code-block-pro-copy-button\"><svg xmlns=\"http:\/\/www.w3.org\/2000\/svg\" style=\"width:24px;height:24px\" fill=\"none\" viewBox=\"0 0 24 24\" stroke=\"currentColor\" stroke-width=\"2\"><path class=\"with-check\" stroke-linecap=\"round\" stroke-linejoin=\"round\" d=\"M9 5H7a2 2 0 00-2 2v12a2 2 0 002 2h10a2 2 0 002-2V7a2 2 0 00-2-2h-2M9 5a2 2 0 002 2h2a2 2 0 002-2M9 5a2 2 0 012-2h2a2 2 0 012 2m-6 9l2 2 4-4\"><\/path><path class=\"without-check\" stroke-linecap=\"round\" stroke-linejoin=\"round\" d=\"M9 5H7a2 2 0 00-2 2v12a2 2 0 002 2h10a2 2 0 002-2V7a2 2 0 00-2-2h-2M9 5a2 2 0 002 2h2a2 2 0 002-2M9 5a2 2 0 012-2h2a2 2 0 012 2\"><\/path><\/svg><\/span><pre class=\"shiki dark-plus\" style=\"background-color: #1E1E1E\" tabindex=\"0\"><code><span class=\"line\"><span style=\"color: #569CD6\">class<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #4EC9B0\">Solution<\/span><span style=\"color: #D4D4D4\">:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">    <\/span><span style=\"color: #569CD6\">def<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #DCDCAA\">twoSum<\/span><span style=\"color: #D4D4D4\">(<\/span><span style=\"color: #9CDCFE\">self<\/span><span style=\"color: #D4D4D4\">, <\/span><span style=\"color: #9CDCFE\">nums<\/span><span style=\"color: #D4D4D4\">: List[<\/span><span style=\"color: #4EC9B0\">int<\/span><span style=\"color: #D4D4D4\">], <\/span><span style=\"color: #9CDCFE\">target<\/span><span style=\"color: #D4D4D4\">: <\/span><span style=\"color: #4EC9B0\">int<\/span><span style=\"color: #D4D4D4\">) -&gt; List[<\/span><span style=\"color: #4EC9B0\">int<\/span><span style=\"color: #D4D4D4\">]:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        n = <\/span><span style=\"color: #DCDCAA\">len<\/span><span style=\"color: #D4D4D4\">(nums)<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #C586C0\">for<\/span><span style=\"color: #D4D4D4\"> i <\/span><span style=\"color: #C586C0\">in<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #DCDCAA\">range<\/span><span style=\"color: #D4D4D4\">(<\/span><span style=\"color: #B5CEA8\">0<\/span><span style=\"color: #D4D4D4\">, n):<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            <\/span><span style=\"color: #C586C0\">for<\/span><span style=\"color: #D4D4D4\"> j <\/span><span style=\"color: #C586C0\">in<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #DCDCAA\">range<\/span><span style=\"color: #D4D4D4\">(i + <\/span><span style=\"color: #B5CEA8\">1<\/span><span style=\"color: #D4D4D4\">, n):<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                <\/span><span style=\"color: #C586C0\">if<\/span><span style=\"color: #D4D4D4\"> nums[i] + nums[j] == target:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                    <\/span><span style=\"color: #C586C0\">return<\/span><span style=\"color: #D4D4D4\"> [i, j]<\/span><\/span><\/code><\/pre><\/div>\n\n\n\n<ol class=\"wp-block-list\">\n<li><strong>Initialization:<\/strong>\n<ol class=\"wp-block-list\">\n<li>n = len(nums): Stores the length of the input array nums.<\/li>\n<\/ol>\n<\/li>\n\n\n\n<li><strong>Outer Loop (<\/strong><strong>for i in range(0, n)<\/strong><strong>):<\/strong>\n<ol class=\"wp-block-list\">\n<li>Iterates over each element in the array starting from the first element.<\/li>\n\n\n\n<li>i represents the index of the first number in the potential pair.<\/li>\n<\/ol>\n<\/li>\n\n\n\n<li><strong>Inner Loop (<\/strong><strong>for j in range(i + 1, n)<\/strong><strong>):<\/strong>\n<ol class=\"wp-block-list\">\n<li>For each element nums[i], iterates over the subsequent elements in the array.<\/li>\n\n\n\n<li>j represents the index of the second number in the potential pair.<\/li>\n\n\n\n<li>Starts from i + 1 to avoid using the same element twice and to prevent redundant checks.<\/li>\n<\/ol>\n<\/li>\n\n\n\n<li><strong>Sum Check (<\/strong><strong>if nums[i] + nums[j] == target<\/strong><strong>):<\/strong>\n<ol class=\"wp-block-list\">\n<li>Checks if the sum of nums[i] and nums[j] equals the target.<\/li>\n\n\n\n<li>If the condition is true, the pair has been found.<\/li>\n<\/ol>\n<\/li>\n\n\n\n<li><strong>Return Statement (<\/strong><strong>return [i, j]<\/strong><strong>):<\/strong>\n<ol class=\"wp-block-list\">\n<li>Returns a list containing the indices [i, j] of the two numbers that add up to the target.<\/li>\n\n\n\n<li>The function exits immediately after finding the first valid pair.<\/li>\n<\/ol>\n<\/li>\n<\/ol>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"4-4-dry-run-\"><strong>4. Dry Run<\/strong><\/h3>\n\n\n\n<p>Let&#8217;s go through the code step by step, using images to illustrate the detailed dry run process.<\/p>\n\n\n\n<figure class=\"wp-block-image size-large\"><img fetchpriority=\"high\" decoding=\"async\" width=\"1024\" height=\"576\" src=\"https:\/\/codeanddebug.in\/blog\/wp-content\/uploads\/2025\/06\/image-6-1024x576.png\" alt=\"\" class=\"wp-image-377\" srcset=\"https:\/\/codeanddebug.in\/blog\/wp-content\/uploads\/2025\/06\/image-6-1024x576.png 1024w, https:\/\/codeanddebug.in\/blog\/wp-content\/uploads\/2025\/06\/image-6-300x169.png 300w, https:\/\/codeanddebug.in\/blog\/wp-content\/uploads\/2025\/06\/image-6-768x432.png 768w, https:\/\/codeanddebug.in\/blog\/wp-content\/uploads\/2025\/06\/image-6-1536x864.png 1536w, https:\/\/codeanddebug.in\/blog\/wp-content\/uploads\/2025\/06\/image-6-150x84.png 150w, https:\/\/codeanddebug.in\/blog\/wp-content\/uploads\/2025\/06\/image-6-450x253.png 450w, https:\/\/codeanddebug.in\/blog\/wp-content\/uploads\/2025\/06\/image-6-1200x675.png 1200w, https:\/\/codeanddebug.in\/blog\/wp-content\/uploads\/2025\/06\/image-6.png 1600w\" sizes=\"(max-width: 1024px) 100vw, 1024px\" \/><\/figure>\n\n\n\n<figure class=\"wp-block-image size-large\"><img decoding=\"async\" width=\"1024\" height=\"576\" src=\"https:\/\/codeanddebug.in\/blog\/wp-content\/uploads\/2025\/06\/image-7-1024x576.png\" alt=\"\" class=\"wp-image-378\" srcset=\"https:\/\/codeanddebug.in\/blog\/wp-content\/uploads\/2025\/06\/image-7-1024x576.png 1024w, https:\/\/codeanddebug.in\/blog\/wp-content\/uploads\/2025\/06\/image-7-300x169.png 300w, https:\/\/codeanddebug.in\/blog\/wp-content\/uploads\/2025\/06\/image-7-768x432.png 768w, https:\/\/codeanddebug.in\/blog\/wp-content\/uploads\/2025\/06\/image-7-1536x864.png 1536w, https:\/\/codeanddebug.in\/blog\/wp-content\/uploads\/2025\/06\/image-7-150x84.png 150w, https:\/\/codeanddebug.in\/blog\/wp-content\/uploads\/2025\/06\/image-7-450x253.png 450w, https:\/\/codeanddebug.in\/blog\/wp-content\/uploads\/2025\/06\/image-7-1200x675.png 1200w, https:\/\/codeanddebug.in\/blog\/wp-content\/uploads\/2025\/06\/image-7.png 1600w\" sizes=\"(max-width: 1024px) 100vw, 1024px\" \/><\/figure>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"5-5-edge-cases-\"><strong>5. Edge Cases<\/strong><\/h3>\n\n\n\n<ul class=\"wp-block-list\">\n<li><strong>No Solution Exists:<\/strong>\n<ul class=\"wp-block-list\">\n<li>According to the problem statement, exactly one solution exists, so this case doesn&#8217;t need to be handled.<\/li>\n<\/ul>\n<\/li>\n\n\n\n<li><strong>Negative Numbers:<\/strong>\n<ul class=\"wp-block-list\">\n<li>The code works correctly with negative numbers as it simply adds and compares sums.<\/li>\n<\/ul>\n<\/li>\n\n\n\n<li><strong>Multiple Valid Pairs:<\/strong>\n<ul class=\"wp-block-list\">\n<li>If multiple pairs add up to the target, the function returns the first pair found due to the order of iteration.<\/li>\n<\/ul>\n<\/li>\n<\/ul>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"6-6-time-and-space-complexity-\"><strong>6. Time and Space Complexity<\/strong><\/h3>\n\n\n\n<ul class=\"wp-block-list\">\n<li><strong>Time Complexity:<\/strong><strong>O(n<\/strong><strong><sup>2<\/sup><\/strong><strong>)<\/strong>\n<ul class=\"wp-block-list\">\n<li>The nested loops result in checking every pair once.<\/li>\n\n\n\n<li>For an array of size n, there are approximately <strong>n(n\u22121)\/2<\/strong> pairs.<\/li>\n<\/ul>\n<\/li>\n\n\n\n<li><strong>Space Complexity:<\/strong><strong>O(1)<\/strong>\n<ul class=\"wp-block-list\">\n<li>The algorithm uses a constant amount of extra space regardless of the input size.<\/li>\n\n\n\n<li>The output list [i, j] has a fixed size of 2.<\/li>\n<\/ul>\n<\/li>\n<\/ul>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<h2 class=\"wp-block-heading\" id=\"7-optimal-solution\">OPTIMAL SOLUTION<\/h2>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"8-1-problem-statement-\"><strong>1. Problem Statement<\/strong><\/h3>\n\n\n\n<p>Given an array of integers nums and an integer target, the task is to find indices of two numbers in the array such that they add up to the target. It is guaranteed that exactly one pair of numbers adds up to the target, and each number can be used at most once.<\/p>\n\n\n\n<p><strong>Input:<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>nums: A list of integers.<\/li>\n\n\n\n<li>target: An integer representing the target sum.<\/li>\n<\/ul>\n\n\n\n<p><strong>Output:<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>A list containing two integers, the indices of the two numbers in nums that add up to target.<\/li>\n<\/ul>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"9-2-intuition-and-approach-\"><strong>2. Intuition and Approach<\/strong><\/h3>\n\n\n\n<p>To solve this problem efficiently, a hash map (dictionary) can be used to keep track of the numbers encountered so far and their indices. The idea is to:<\/p>\n\n\n\n<ol class=\"wp-block-list\">\n<li><strong>Iterate through the array:<\/strong>\n<ul class=\"wp-block-list\">\n<li>For each element nums[i], calculate the complement remaining = target &#8211; nums[i], which is the number needed to reach the target.<\/li>\n<\/ul>\n<\/li>\n\n\n\n<li><strong>Check for the complement:<\/strong>\n<ul class=\"wp-block-list\">\n<li>If the complement remaining is already in the hash map, it means a previous number can be paired with the current number to reach the target.<\/li>\n<\/ul>\n<\/li>\n\n\n\n<li><strong>Return the result:<\/strong>\n<ul class=\"wp-block-list\">\n<li>When such a pair is found, return the indices of the complement and the current number.<\/li>\n<\/ul>\n<\/li>\n\n\n\n<li><strong>Update the hash map:<\/strong>\n<ul class=\"wp-block-list\">\n<li>If the complement is not found, store the current number and its index in the hash map for future reference.<\/li>\n<\/ul>\n<\/li>\n<\/ol>\n\n\n\n<p>This approach allows finding the required pair in a single pass through the array, resulting in an efficient <strong>O(n)<\/strong> time complexity.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"10-3-code-\"><strong>3. Code<\/strong><\/h3>\n\n\n\n<div class=\"wp-block-kevinbatdorf-code-block-pro\" data-code-block-pro-font-family=\"Code-Pro-JetBrains-Mono\" style=\"font-size:.875rem;font-family:Code-Pro-JetBrains-Mono,ui-monospace,SFMono-Regular,Menlo,Monaco,Consolas,monospace;line-height:1.25rem;--cbp-tab-width:2;tab-size:var(--cbp-tab-width, 2)\"><span style=\"display:block;padding:16px 0 0 16px;margin-bottom:-1px;width:100%;text-align:left;background-color:#1E1E1E\"><svg xmlns=\"http:\/\/www.w3.org\/2000\/svg\" width=\"54\" height=\"14\" viewBox=\"0 0 54 14\"><g fill=\"none\" fill-rule=\"evenodd\" transform=\"translate(1 1)\"><circle cx=\"6\" cy=\"6\" r=\"6\" fill=\"#FF5F56\" stroke=\"#E0443E\" stroke-width=\".5\"><\/circle><circle cx=\"26\" cy=\"6\" r=\"6\" fill=\"#FFBD2E\" stroke=\"#DEA123\" stroke-width=\".5\"><\/circle><circle cx=\"46\" cy=\"6\" r=\"6\" fill=\"#27C93F\" stroke=\"#1AAB29\" stroke-width=\".5\"><\/circle><\/g><\/svg><\/span><span role=\"button\" tabindex=\"0\" data-code=\"class Solution:\n    def twoSum(self, nums: List[int], target: int) -&gt; List[int]:\n        n = len(nums)\n        hash_map = dict()\n        for i in range(n):\n            remaining = target - nums[i]\n            if remaining in hash_map:\n                return [hash_map[remaining], i]\n            hash_map[nums[i]] = i\" style=\"color:#D4D4D4;display:none\" aria-label=\"Copy\" class=\"code-block-pro-copy-button\"><svg xmlns=\"http:\/\/www.w3.org\/2000\/svg\" style=\"width:24px;height:24px\" fill=\"none\" viewBox=\"0 0 24 24\" stroke=\"currentColor\" stroke-width=\"2\"><path class=\"with-check\" stroke-linecap=\"round\" stroke-linejoin=\"round\" d=\"M9 5H7a2 2 0 00-2 2v12a2 2 0 002 2h10a2 2 0 002-2V7a2 2 0 00-2-2h-2M9 5a2 2 0 002 2h2a2 2 0 002-2M9 5a2 2 0 012-2h2a2 2 0 012 2m-6 9l2 2 4-4\"><\/path><path class=\"without-check\" stroke-linecap=\"round\" stroke-linejoin=\"round\" d=\"M9 5H7a2 2 0 00-2 2v12a2 2 0 002 2h10a2 2 0 002-2V7a2 2 0 00-2-2h-2M9 5a2 2 0 002 2h2a2 2 0 002-2M9 5a2 2 0 012-2h2a2 2 0 012 2\"><\/path><\/svg><\/span><pre class=\"shiki dark-plus\" style=\"background-color: #1E1E1E\" tabindex=\"0\"><code><span class=\"line\"><span style=\"color: #569CD6\">class<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #4EC9B0\">Solution<\/span><span style=\"color: #D4D4D4\">:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">    <\/span><span style=\"color: #569CD6\">def<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #DCDCAA\">twoSum<\/span><span style=\"color: #D4D4D4\">(<\/span><span style=\"color: #9CDCFE\">self<\/span><span style=\"color: #D4D4D4\">, <\/span><span style=\"color: #9CDCFE\">nums<\/span><span style=\"color: #D4D4D4\">: List[<\/span><span style=\"color: #4EC9B0\">int<\/span><span style=\"color: #D4D4D4\">], <\/span><span style=\"color: #9CDCFE\">target<\/span><span style=\"color: #D4D4D4\">: <\/span><span style=\"color: #4EC9B0\">int<\/span><span style=\"color: #D4D4D4\">) -&gt; List[<\/span><span style=\"color: #4EC9B0\">int<\/span><span style=\"color: #D4D4D4\">]:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        n = <\/span><span style=\"color: #DCDCAA\">len<\/span><span style=\"color: #D4D4D4\">(nums)<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        hash_map = <\/span><span style=\"color: #4EC9B0\">dict<\/span><span style=\"color: #D4D4D4\">()<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #C586C0\">for<\/span><span style=\"color: #D4D4D4\"> i <\/span><span style=\"color: #C586C0\">in<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #DCDCAA\">range<\/span><span style=\"color: #D4D4D4\">(n):<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            remaining = target - nums[i]<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            <\/span><span style=\"color: #C586C0\">if<\/span><span style=\"color: #D4D4D4\"> remaining <\/span><span style=\"color: #569CD6\">in<\/span><span style=\"color: #D4D4D4\"> hash_map:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                <\/span><span style=\"color: #C586C0\">return<\/span><span style=\"color: #D4D4D4\"> [hash_map[remaining], i]<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            hash_map[nums[i]] = i<\/span><\/span><\/code><\/pre><\/div>\n\n\n\n<ul class=\"wp-block-list\">\n<li><strong>Initialization:<\/strong>\n<ul class=\"wp-block-list\">\n<li>n = len(nums): Determine the length of the array.<\/li>\n\n\n\n<li>hash_map = dict(): Initialize an empty dictionary to store numbers and their indices.<\/li>\n<\/ul>\n<\/li>\n\n\n\n<li><strong>Iteration over the array:<\/strong>\n<ul class=\"wp-block-list\">\n<li>for i in range(n):: Loop through each index i in the array.\n<ul class=\"wp-block-list\">\n<li><strong>Calculate the complement:<\/strong>\n<ul class=\"wp-block-list\">\n<li>remaining = target &#8211; nums[i]: Compute the number needed to reach the target with the current number.<\/li>\n<\/ul>\n<\/li>\n\n\n\n<li><strong>Check if the complement exists:<\/strong>\n<ul class=\"wp-block-list\">\n<li>if remaining in hash_map:: If the complement is in the hash map, a valid pair is found.\n<ul class=\"wp-block-list\">\n<li><strong>Return the indices:<\/strong>\n<ul class=\"wp-block-list\">\n<li>return [hash_map[remaining], i]: Return the indices of the complement and the current number.<\/li>\n<\/ul>\n<\/li>\n<\/ul>\n<\/li>\n<\/ul>\n<\/li>\n\n\n\n<li><strong>Update the hash map:<\/strong>\n<ul class=\"wp-block-list\">\n<li>hash_map[nums[i]] = i: Add the current number and its index to the hash map for future reference.<\/li>\n<\/ul>\n<\/li>\n<\/ul>\n<\/li>\n<\/ul>\n<\/li>\n<\/ul>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"11-4-dry-run-\"><strong>4. Dry Run<\/strong><\/h3>\n\n\n\n<p>Let&#8217;s go through the code step by step, using images to illustrate the detailed dry run process.<\/p>\n\n\n\n<figure class=\"wp-block-image size-large\"><img decoding=\"async\" width=\"1024\" height=\"576\" src=\"https:\/\/codeanddebug.in\/blog\/wp-content\/uploads\/2025\/06\/image-8-1024x576.png\" alt=\"\" class=\"wp-image-379\" srcset=\"https:\/\/codeanddebug.in\/blog\/wp-content\/uploads\/2025\/06\/image-8-1024x576.png 1024w, https:\/\/codeanddebug.in\/blog\/wp-content\/uploads\/2025\/06\/image-8-300x169.png 300w, https:\/\/codeanddebug.in\/blog\/wp-content\/uploads\/2025\/06\/image-8-768x432.png 768w, https:\/\/codeanddebug.in\/blog\/wp-content\/uploads\/2025\/06\/image-8-1536x864.png 1536w, https:\/\/codeanddebug.in\/blog\/wp-content\/uploads\/2025\/06\/image-8-150x84.png 150w, https:\/\/codeanddebug.in\/blog\/wp-content\/uploads\/2025\/06\/image-8-450x253.png 450w, https:\/\/codeanddebug.in\/blog\/wp-content\/uploads\/2025\/06\/image-8-1200x675.png 1200w, https:\/\/codeanddebug.in\/blog\/wp-content\/uploads\/2025\/06\/image-8.png 1600w\" sizes=\"(max-width: 1024px) 100vw, 1024px\" \/><\/figure>\n\n\n\n<figure class=\"wp-block-image size-large\"><img loading=\"lazy\" decoding=\"async\" width=\"1024\" height=\"576\" src=\"https:\/\/codeanddebug.in\/blog\/wp-content\/uploads\/2025\/06\/image-9-1024x576.png\" alt=\"\" class=\"wp-image-380\" srcset=\"https:\/\/codeanddebug.in\/blog\/wp-content\/uploads\/2025\/06\/image-9-1024x576.png 1024w, https:\/\/codeanddebug.in\/blog\/wp-content\/uploads\/2025\/06\/image-9-300x169.png 300w, https:\/\/codeanddebug.in\/blog\/wp-content\/uploads\/2025\/06\/image-9-768x432.png 768w, https:\/\/codeanddebug.in\/blog\/wp-content\/uploads\/2025\/06\/image-9-1536x864.png 1536w, https:\/\/codeanddebug.in\/blog\/wp-content\/uploads\/2025\/06\/image-9-150x84.png 150w, https:\/\/codeanddebug.in\/blog\/wp-content\/uploads\/2025\/06\/image-9-450x253.png 450w, https:\/\/codeanddebug.in\/blog\/wp-content\/uploads\/2025\/06\/image-9-1200x675.png 1200w, https:\/\/codeanddebug.in\/blog\/wp-content\/uploads\/2025\/06\/image-9.png 1600w\" sizes=\"(max-width: 1024px) 100vw, 1024px\" \/><\/figure>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"12-5-edge-cases-\"><strong>5. Edge Cases<\/strong><\/h3>\n\n\n\n<ul class=\"wp-block-list\">\n<li><strong>Negative Numbers:<\/strong>\n<ul class=\"wp-block-list\">\n<li>The method works with negative numbers since addition and subtraction are valid for negative values.<\/li>\n<\/ul>\n<\/li>\n\n\n\n<li><strong>Multiple Valid Pairs:<\/strong>\n<ul class=\"wp-block-list\">\n<li>If multiple pairs add up to the target, the function returns the first pair found during iteration.<\/li>\n<\/ul>\n<\/li>\n\n\n\n<li><strong>Single Element:<\/strong>\n<ul class=\"wp-block-list\">\n<li>Since the problem guarantees exactly one solution and that we cannot use the same element twice, arrays with fewer than two elements are not considered.<\/li>\n<\/ul>\n<\/li>\n<\/ul>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"13-6-time-and-space-complexity-\"><strong>6. Time and Space Complexity<\/strong><\/h3>\n\n\n\n<ul class=\"wp-block-list\">\n<li><strong>Time Complexity:<\/strong><strong>O(n)<\/strong>\n<ul class=\"wp-block-list\">\n<li>The array is traversed once, and each lookup or insertion in the hash map is <strong>O(1)<\/strong> on average.<\/li>\n<\/ul>\n<\/li>\n\n\n\n<li><strong>Space Complexity:<\/strong><strong>O(n)<\/strong>\n<ul class=\"wp-block-list\">\n<li>In the worst case, all elements are stored in the hash map.<\/li>\n<\/ul>\n<\/li>\n<\/ul>\n\n\n\n<div class=\"wp-block-buttons is-content-justification-center is-layout-flex wp-container-core-buttons-is-layout-16018d1d wp-block-buttons-is-layout-flex\">\n<div class=\"wp-block-button\"><a class=\"wp-block-button__link wp-element-button\" href=\"https:\/\/www.codeanddebug.in\/course\/zero-to-hero-python-dsa\" target=\"_blank\" rel=\"noreferrer noopener\">Join our Advance DSA COURSE<\/a><\/div>\n<\/div>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<p><em>For any changes to the article, kindly email at <a href=\"mailto:code@codeanddebug.in\">code@codeanddebug.in<\/a> or contact us at <a href=\"tel:+91-9712928220\">+91-9712928220<\/a>.<\/em><\/p>\n\n\n\n<p><\/p>\n","protected":false},"excerpt":{"rendered":"<p>Given an array of integers&nbsp;nums&nbsp;and an integer&nbsp;target, return&nbsp;indices of the two numbers such that they add up to&nbsp;target. You may assume that each input would have&nbsp;exactly&nbsp;one solution, and you may not use the&nbsp;same&nbsp;element twice. You can return the answer in any order. Here&#8217;s the [Problem Link] to begin with. Example 1:Input: nums = [2,7,11,15], target<\/p>\n","protected":false},"author":1,"featured_media":383,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[3,4],"tags":[7,8,9],"class_list":{"0":"post-375","1":"post","2":"type-post","3":"status-publish","4":"format-standard","5":"has-post-thumbnail","7":"category-data-structures-and-algorithm","8":"category-beginner","9":"tag-array","10":"tag-easy","11":"tag-hash-table"},"featured_image_src":"https:\/\/codeanddebug.in\/blog\/wp-content\/uploads\/2025\/06\/two-sum-featured-image.png","author_info":{"display_name":"codeanddebug","author_link":"https:\/\/codeanddebug.in\/blog\/author\/codeanddebug\/"},"_links":{"self":[{"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/posts\/375","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/comments?post=375"}],"version-history":[{"count":2,"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/posts\/375\/revisions"}],"predecessor-version":[{"id":416,"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/posts\/375\/revisions\/416"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/media\/383"}],"wp:attachment":[{"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/media?parent=375"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/categories?post=375"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/tags?post=375"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}