{"id":834,"date":"2026-04-12T17:01:27","date_gmt":"2026-04-12T17:01:27","guid":{"rendered":"https:\/\/funwithdev.com\/?page_id=834"},"modified":"2026-04-12T17:02:37","modified_gmt":"2026-04-12T17:02:37","slug":"two-sum-find-the-set-of-pairs-for-a-target-sum","status":"publish","type":"page","link":"https:\/\/funwithdev.com\/?page_id=834","title":{"rendered":"Two Sum"},"content":{"rendered":"\n

The Two Sum Problem: A Comprehensive Guide to Brute Force vs Hash Map Solutions<\/h1>\n\n\n\n

Introduction<\/h2>\n\n\n\n

The “Two Sum” problem is a classic coding interview question and a fundamental algorithmic challenge that teaches important problem-solving concepts. The problem is deceptively simple to understand but offers rich learning opportunities when optimizing the solution.<\/p>\n\n\n\n

Problem Statement:<\/strong> Given an array of integers and a target sum, find two indices in the array such that the numbers at those indices add up to the target. Return the indices (or an empty array if no solution exists).<\/p>\n\n\n\n

Example:<\/strong><\/p>\n\n\n\n

const array = [2, 7, 11, 15];\nconst target = 9;\n\/\/ Expected output: [0, 1] because array[0] + array[1] = 2 + 7 = 9<\/em>\n<\/code><\/pre>\n\n\n\n
Approach 1: Brute Force Solution<\/h2>\n\n\n\n
How It Works<\/h3>\n\n\n\n
The brute force approach uses nested loops to check every possible pair of elements in the array:<\/p>\n\n\n\n
function findTwoSum(array, targetSum) {\n    let arrayList = [];\n    \n    if(array === null)\n        return [];\n    \n    let n = array.length;\n    \n    \/\/ Outer loop: iterate through each element<\/em>\n    for(let i = 0; i < n; i++) {\n        \/\/ Inner loop: compare with all elements after it<\/em>\n        for(let j = i + 1; j < n; j++) {\n            if(array[i] + array[j] === targetSum) {\n                arrayList.push([i, j]);\n            }\n        }\n    }\n    \n    return arrayList;\n}\n<\/code><\/pre>\n\n\n\n
Algorithm Breakdown<\/h3>\n\n\n\n
    \n
  1. Null Check<\/strong>: First, verify the array is not null to avoid runtime errors<\/li>\n\n\n\n
  2. Outer Loop<\/strong>: Iterate through each element (index\u00a0i<\/code>)<\/li>\n\n\n\n
  3. Inner Loop<\/strong>: For each element at\u00a0i<\/code>, compare it with all elements after it (index\u00a0j<\/code>)<\/li>\n\n\n\n
  4. Comparison<\/strong>: If the sum equals the target, add the index pair\u00a0[i, j]<\/code>\u00a0to the result<\/li>\n\n\n\n
  5. Return<\/strong>: Return all found pairs<\/li>\n<\/ol>\n\n\n\n
    Complexity Analysis<\/h3>\n\n\n\n
      \n
    • Time Complexity: O(N\u00b2)<\/strong>\n
        \n
      • The nested loops create a quadratic relationship with input size<\/li>\n\n\n\n
      • For an array of size N, we perform approximately N\u00d7(N-1)\/2 comparisons<\/li>\n\n\n\n
      • In the worst case (no valid pair), every element is compared with every other element<\/li>\n\n\n\n
      • This becomes prohibitively slow for large datasets<\/li>\n<\/ul>\n<\/li>\n\n\n\n
      • Space Complexity: O(K)<\/strong>\u00a0where K is the number of valid pairs\n
          \n
        • The algorithm stores each pair of indices in the result array<\/li>\n\n\n\n
        • No additional data structures are used beyond the output array<\/li>\n\n\n\n
        • The space grows only with the number of solutions found<\/li>\n<\/ul>\n<\/li>\n<\/ul>\n\n\n\n
          Pros and Cons<\/h3>\n\n\n\n
          Pros:<\/strong><\/p>\n\n\n\n
            \n
          • \u2705 Simple to understand and implement<\/li>\n\n\n\n
          • \u2705 No additional data structures needed<\/li>\n\n\n\n
          • \u2705 Finds ALL pairs (not just one)<\/li>\n\n\n\n
          • \u2705 Works in-place for most operations<\/li>\n<\/ul>\n\n\n\n
            Cons:<\/strong><\/p>\n\n\n\n
              \n
            • \u274c Extremely slow for large datasets (O(N\u00b2) is problematic when N is large)<\/li>\n\n\n\n
            • \u274c Inefficient: rechecks combinations unnecessarily<\/li>\n\n\n\n
            • \u274c Not scalable for production systems with large arrays<\/li>\n\n\n\n
            • \u274c Performs redundant calculations<\/li>\n<\/ul>\n\n\n\n
              \n\n\n\n
              Approach 2: Hash Map Solution<\/h2>\n\n\n\n
              How It Works<\/h3>\n\n\n\n
              The hash map approach trades space for time by using a Map to achieve O(N) time complexity:<\/p>\n\n\n\n
              function twoSumHashMap(nums, target) {\n    const map = new Map();\n    \n    for (let i = 0; i < nums.length; i++) {\n        \/\/ Calculate what number we need to find<\/em>\n        const complement = target - nums[i];\n        \n        \/\/ Check if we've already seen the complement<\/em>\n        if (map.has(complement)) {\n            return [map.get(complement), i];\n        }\n        \n        \/\/ Store current number and its index for future lookups<\/em>\n        map.set(nums[i], i);\n    }\n    \n    return [];\n}\n<\/code><\/pre>\n\n\n\n
              Algorithm Breakdown<\/h3>\n\n\n\n
                \n
              1. Initialize Map<\/strong>: Create an empty Map to store seen elements and their indices<\/li>\n\n\n\n
              2. Single Pass<\/strong>: Iterate through the array once (index\u00a0i<\/code>)<\/li>\n\n\n\n
              3. Calculate Complement<\/strong>: For the current element, calculate what number we need:\u00a0complement = target - nums[i]<\/code><\/li>\n\n\n\n
              4. Check Map<\/strong>: Look up if the complement exists in the map (O(1) average case)<\/li>\n\n\n\n
              5. Found or Store<\/strong>:\n
                  \n
                • If complement exists: return the pair of indices immediately<\/li>\n\n\n\n
                • If not found: store the current element and its index in the map<\/li>\n<\/ul>\n<\/li>\n\n\n\n
                • Return<\/strong>: If the loop completes without finding a pair, return empty array<\/li>\n<\/ol>\n\n\n\n
                  Algorithm Example Walk-Through<\/h3>\n\n\n\n
                  const array = [2, 7, 11, 15];\nconst target = 9;\n\n\/\/ Iteration 1: i=0, nums[0]=2<\/em>\n  complement = 9 - 2 = 7\n  map.has(7)? \u2192 false\n  map.set(2, 0) \u2192 map: {2: 0}\n\n\/\/ Iteration 2: i=1, nums[1]=7<\/em>\n  complement = 9 - 7 = 2\n  map.has(2)? \u2192 true! (we stored it in iteration 1)\n  return [map.get(2), 1] \u2192 [0, 1] \u2713\n<\/code><\/pre>\n\n\n\n
                  Complexity Analysis<\/h3>\n\n\n\n
                    \n
                  • Time Complexity: O(N)<\/strong>\n
                      \n
                    • Single pass through the array<\/li>\n\n\n\n
                    • Each iteration performs constant-time operations:\n
                        \n
                      • Subtraction: O(1)<\/li>\n\n\n\n
                      • Map lookup (has): O(1) average case<\/li>\n\n\n\n
                      • Map insertion (set): O(1) average case<\/li>\n<\/ul>\n<\/li>\n\n\n\n
                      • Total: N \u00d7 O(1) = O(N)<\/li>\n<\/ul>\n<\/li>\n\n\n\n
                      • Space Complexity: O(N)<\/strong>\n
                          \n
                        • Stores up to N elements in the hash map (worst case if no pair found)<\/li>\n\n\n\n
                        • This is the trade-off: use more space to achieve faster time<\/li>\n<\/ul>\n<\/li>\n<\/ul>\n\n\n\n
                          Pros and Cons<\/h3>\n\n\n\n
                          Pros:<\/strong><\/p>\n\n\n\n
                            \n
                          • \u2705 Excellent time complexity: O(N) is linear and highly scalable<\/li>\n\n\n\n
                          • \u2705 Much faster for large datasets<\/li>\n\n\n\n
                          • \u2705 Efficient in production systems<\/li>\n\n\n\n
                          • \u2705 Early exit: returns immediately upon finding a pair<\/li>\n\n\n\n
                          • \u2705 Single pass through data<\/li>\n<\/ul>\n\n\n\n
                            Cons:<\/strong><\/p>\n\n\n\n
                              \n
                            • \u274c Uses O(N) extra space<\/li>\n\n\n\n
                            • \u274c Only finds the first pair (not all pairs)<\/li>\n\n\n\n
                            • \u274c Slightly more complex logic<\/li>\n\n\n\n
                            • \u274c Hash map overhead (though minimal for most cases)<\/li>\n\n\n\n
                            • \u274c Not ideal if memory is extremely constrained<\/li>\n<\/ul>\n\n\n\n
                              \n\n\n\n
                              Head-to-Head Comparison<\/h2>\n\n\n\n
                              Aspect<\/th>Brute Force<\/th>Hash Map<\/th><\/tr><\/thead>
                              Time Complexity<\/strong><\/td>O(N\u00b2)<\/td>O(N)<\/td><\/tr>
                              Space Complexity<\/strong><\/td>O(K)<\/td>O(N)<\/td><\/tr>
                              Best Case<\/strong><\/td>O(N\u00b2) when no pair exists<\/td>O(1) if pair at start<\/td><\/tr>
                              Average Case<\/strong><\/td>O(N\u00b2)<\/td>O(N)<\/td><\/tr>
                              Worst Case<\/strong><\/td>O(N\u00b2)<\/td>O(N)<\/td><\/tr>
                              Scalability<\/strong><\/td>Poor<\/td>Excellent<\/td><\/tr>
                              Memory Usage<\/strong><\/td>Minimal<\/td>Higher<\/td><\/tr>
                              Simplicity<\/strong><\/td>Very simple<\/td>Moderate<\/td><\/tr>
                              Finds Pairs<\/strong><\/td>All pairs<\/td>First pair<\/td><\/tr>
                              Early Exit<\/strong><\/td>No<\/td>Yes<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n
                              Performance Comparison: Real Numbers<\/h2>\n\n\n\n
                              For an array of 10,000 elements<\/strong>:<\/p>\n\n\n\n
                                \n
                              • Brute Force<\/strong>: ~50,000,000 comparisons (approximately 100-500ms)<\/li>\n\n\n\n
                              • Hash Map<\/strong>: ~10,000 operations (approximately 1-5ms)<\/li>\n<\/ul>\n\n\n\n
                                Speed improvement: 20-100x faster<\/strong> \u26a1<\/p>\n\n\n\n
                                For an array of 100,000 elements<\/strong>:<\/p>\n\n\n\n
                                  \n
                                • Brute Force<\/strong>: ~5,000,000,000 comparisons (seconds or minutes)<\/li>\n\n\n\n
                                • Hash Map<\/strong>: ~100,000 operations (10-50ms)<\/li>\n<\/ul>\n\n\n\n
                                  Speed improvement: 100-1000x faster<\/strong> \ud83d\ude80<\/p>\n\n\n\n
                                  When to Use Each Approach<\/h2>\n\n\n\n
                                  Use Brute Force When:<\/h3>\n\n\n\n
                                    \n
                                  • The array is very small (< 100 elements)<\/li>\n\n\n\n
                                  • You need to find ALL pairs, not just one<\/li>\n\n\n\n
                                  • Memory is extremely limited<\/li>\n\n\n\n
                                  • You’re in a learning environment prioritizing clarity<\/li>\n\n\n\n
                                  • The simplicity of code is more important than performance<\/li>\n<\/ul>\n\n\n\n
                                    Use Hash Map When:<\/h3>\n\n\n\n
                                      \n
                                    • The array is large (\u2265 1000 elements)<\/li>\n\n\n\n
                                    • Finding one valid pair is sufficient<\/li>\n\n\n\n
                                    • Performance is critical<\/li>\n\n\n\n
                                    • You’re in a production environment<\/li>\n\n\n\n
                                    • You have adequate memory available<\/li>\n\n\n\n
                                    • You need to handle real-world datasets<\/li>\n<\/ul>\n\n\n\n
                                      Key Insights<\/h2>\n\n\n\n
                                      1. Trade-offs in Computer Science<\/h3>\n\n\n\n
                                      This problem perfectly illustrates a fundamental principle: space-time trade-off<\/strong>. We can improve time complexity by using additional space (the hash map).<\/p>\n\n\n\n
                                      2. Optimization Matters<\/h3>\n\n\n\n
                                      The difference between O(N\u00b2) and O(N) becomes dramatic with large datasets. This single optimization can mean the difference between a solution that takes milliseconds vs. one that takes hours.<\/p>\n\n\n\n
                                      3. Context Dependency<\/h3>\n\n\n\n
                                      There’s no universally “best” solution\u2014the right choice depends on constraints:<\/p>\n\n\n\n
                                        \n
                                      • If space is unlimited and time is critical \u2192 Hash Map<\/li>\n\n\n\n
                                      • If space is limited and time is less critical \u2192 Brute Force<\/li>\n\n\n\n
                                      • If both matter \u2192 Consider the domain and choose accordingly<\/li>\n<\/ul>\n\n\n\n
                                        4. Why Interviews Ask This Question<\/h3>\n\n\n\n
                                        Interviewers ask about Two Sum because it:<\/p>\n\n\n\n
                                          \n
                                        • Tests problem-solving ability<\/li>\n\n\n\n
                                        • Reveals optimization skills<\/li>\n\n\n\n
                                        • Demonstrates understanding of data structures<\/li>\n\n\n\n
                                        • Shows awareness of time\/space complexity<\/li>\n\n\n\n
                                        • Assesses coding communication skills<\/li>\n<\/ul>\n\n\n\n
                                          Code Comparison: Side by Side<\/h2>\n\n\n\n
                                          Brute Force<\/h3>\n\n\n\n
                                          function findTwoSum(array, targetSum) {\n    let arrayList = [];\n    if(array === null) return [];\n    let n = array.length;\n    \n    for(let i = 0; i < n; i++) {\n        for(let j = i + 1; j < n; j++) {\n            if(array[i] + array[j] === targetSum) {\n                arrayList.push([i, j]);\n            }\n        }\n    }\n    return arrayList;\n}\n<\/code><\/pre>\n\n\n\n
                                          Hash Map<\/h3>\n\n\n\n
                                          function twoSumHashMap(nums, target) {\n    const map = new Map();\n    \n    for (let i = 0; i < nums.length; i++) {\n        const complement = target - nums[i];\n        if (map.has(complement)) {\n            return [map.get(complement), i];\n        }\n        map.set(nums[i], i);\n    }\n    return [];\n}\n<\/code><\/pre>\n\n\n\n
                                          The hash map solution is slightly longer but dramatically more efficient.<\/p>\n\n\n\n
                                          Variations and Extensions<\/h2>\n\n\n\n
                                          Variation 1: Three Sum Problem<\/h3>\n\n\n\n
                                          Challenge<\/strong>: Find three indices whose values sum to a target<\/p>\n\n\n\n
                                            \n
                                          • Simple approach<\/strong>: Modify brute force to use three nested loops (O(N\u00b3))<\/li>\n\n\n\n
                                          • Better approach<\/strong>: Fix one element and apply two-sum to the rest<\/li>\n\n\n\n
                                          • Time complexity<\/strong>: O(N\u00b2)<\/li>\n<\/ul>\n\n\n\n
                                            Variation 2: Four Sum Problem<\/h3>\n\n\n\n
                                            Challenge<\/strong>: Find four indices whose values sum to a target<\/p>\n\n\n\n
                                              \n
                                            • Uses similar strategy: fix elements and reduce to simpler problem<\/li>\n\n\n\n
                                            • Time complexity: O(N\u00b3) with optimization<\/li>\n<\/ul>\n\n\n\n
                                              Variation 3: Return Values Instead of Indices<\/h3>\n\n\n\n
                                              Challenge<\/strong>: Return the actual values instead of indices<\/p>\n\n\n\n
                                                \n
                                              • Minor modification to either solution<\/li>\n\n\n\n
                                              • Hash map becomes even more efficient<\/li>\n<\/ul>\n\n\n\n
                                                Variation 4: Multiple Solutions Allowed<\/h3>\n\n\n\n
                                                Challenge<\/strong>: Find all unique pairs (not just one)<\/p>\n\n\n\n
                                                  \n
                                                • Brute force excels here (already finds all)<\/li>\n\n\n\n
                                                • Hash map needs modification to track all solutions<\/li>\n<\/ul>\n\n\n\n
                                                  Testing Your Implementation<\/h2>\n\n\n\n
                                                  Here are key test cases to validate your implementation:<\/p>\n\n\n\n
                                                  \/\/ Test 1: Basic case<\/em>\ntwoSum([2, 7, 11, 15], 9) \u2192 [0, 1]\n\n\/\/ Test 2: No solution<\/em>\ntwoSum([1, 2, 3], 7) \u2192 []\n\n\/\/ Test 3: Negative numbers<\/em>\ntwoSum([-1, -2, -3, 5, 10], 7) \u2192 [2, 4] or [3, 4]\n\n\/\/ Test 4: Duplicates<\/em>\ntwoSum([3, 3, 4], 6) \u2192 [0, 1]\n\n\/\/ Test 5: Empty array<\/em>\ntwoSum([], 5) \u2192 []\n\n\/\/ Test 6: Single element<\/em>\ntwoSum([5], 10) \u2192 []\n\n\/\/ Test 7: Large numbers<\/em>\ntwoSum([1000000, 2000000, 3000000], 5000000) \u2192 [1, 2]\n<\/code><\/pre>\n\n\n\n
                                                  Conclusion<\/h2>\n\n\n\n
                                                  The Two Sum problem is more than just a coding challenge\u2014it’s a lesson in algorithmic thinking and optimization. By comparing the brute force and hash map approaches, we’ve learned:<\/p>\n\n\n\n
                                                    \n
                                                  1. Multiple solutions exist<\/strong>\u00a0with different trade-offs<\/li>\n\n\n\n
                                                  2. Understanding complexity<\/strong>\u00a0is crucial for scalability<\/li>\n\n\n\n
                                                  3. Context determines the right choice<\/strong>\u00a0(constraints matter)<\/li>\n\n\n\n
                                                  4. Optimization techniques<\/strong>\u00a0like hash maps can provide dramatic improvements<\/li>\n\n\n\n
                                                  5. Good engineers think about performance<\/strong>\u00a0from the start<\/li>\n<\/ol>\n\n\n\n
                                                    The hash map solution is the clear winner for most real-world scenarios, achieving a 20-1000x improvement depending on input size. However, understanding the brute force approach is equally important because it demonstrates clear, logical thinking and provides a foundation for understanding optimization.<\/p>\n\n\n\n
                                                    Remember: The best algorithm is one that solves the problem correctly within the constraints of your system.<\/strong><\/p>\n\n\n\n
                                                    \n\n\n\n
                                                    References<\/h2>\n\n\n\n
                                                      \n
                                                    • Data Structures<\/strong>: Hash Maps \/ Dictionaries<\/li>\n\n\n\n
                                                    • Algorithms<\/strong>: Linear Search vs Hash Table Lookup<\/li>\n\n\n\n
                                                    • Complexity Theory<\/strong>: Big O Notation (O(1), O(N), O(N\u00b2))<\/li>\n\n\n\n
                                                    • Interview Prep<\/strong>: LeetCode Problem #1 (Two Sum)<\/li>\n<\/ul>\n\n\n\n
                                                      <\/p>\n","protected":false},"excerpt":{"rendered":"
                                                      The Two Sum Problem: A Comprehensive Guide to Brute Force vs Hash Map Solutions Introduction The “Two Sum” problem is a classic coding interview question and a fundamental algorithmic challenge that teaches important problem-solving concepts. The problem is deceptively simple to understand but offers rich learning opportunities when optimizing the solution. Problem Statement: Given an array […]<\/p>\n","protected":false},"author":2,"featured_media":0,"parent":0,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"","meta":{"footnotes":""},"class_list":["post-834","page","type-page","status-publish","hentry"],"_links":{"self":[{"href":"https:\/\/funwithdev.com\/index.php?rest_route=\/wp\/v2\/pages\/834","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/funwithdev.com\/index.php?rest_route=\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/funwithdev.com\/index.php?rest_route=\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/funwithdev.com\/index.php?rest_route=\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/funwithdev.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=834"}],"version-history":[{"count":3,"href":"https:\/\/funwithdev.com\/index.php?rest_route=\/wp\/v2\/pages\/834\/revisions"}],"predecessor-version":[{"id":838,"href":"https:\/\/funwithdev.com\/index.php?rest_route=\/wp\/v2\/pages\/834\/revisions\/838"}],"wp:attachment":[{"href":"https:\/\/funwithdev.com\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=834"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}