Grokking the Coding Interview: Patterns for Coding Questions
Vote

0% completed

​

Solution: Pair with Target Sum

Problem Statement

Why this is a Two Pointers problem

Solution

Step-by-Step Algorithm

Code

Time Complexity

Space Complexity

An Alternate approach

Step-by-step Algorithm

Code

Time Complexity

Space Complexity

Problem Statement

Given an array of numbers sorted in ascending order and a target sum, find a pair in the array whose sum is equal to the given target. If no such pair exists return [-1, -1].

Write a function to return the indices of the two numbers (i.e. the pair) such that they add up to the given target.

Example 1:

Input: [1, 2, 3, 4, 6], target=6
Output: [1, 3]
Explanation: The numbers at index 1 and 3 add up to 6: 2+4=6

Example 2:

Input: [2, 5, 9, 11], target=11
Output: [0, 2]
Explanation: The numbers at index 0 and 2 add up to 11: 2+9=11

Constraints:

  • 2 <= arr.length <= 10<sup>4</sup>
  • -10<sup>9</sup> <= arr[i] <= 10<sup>9</sup>
  • -10<sup>9</sup> <= target <= 10<sup>9</sup>

Why this is a Two Pointers problem

What the question saysThe signal it matches
"sorted in ascending order"the input is sorted
"find a pair in the array whose sum is equal to the given target"you are asked for a pair that meets a condition, here a target sum
checking every pair means a loop inside a loop, and the array holds up to 10,000 numbersyour first idea is two nested loops, which is about 50 million pairs here

Sorted input plus a pair with a condition gives the converging variant: one pointer at each end, moving inward.

The closest alternative. A hash map is the alternative here. The question asks for indices. The introduction warns that this pattern is wrong when the array is unsorted and the indices are needed, because sorting destroys them.

Here the array arrives sorted. No sorting step is needed, so the indices survive. If the array were unsorted, this would be a hash map problem.

Solution

Since the given array is sorted, a brute-force solution could be to iterate through the array, taking one number at a time and searching for the second number through Binary Search. The time complexity of this algorithm will be O(N*logN). Can we do better than this?

To solve this problem, we can use a two-pointer approach. This approach is efficient because it takes advantage of the sorted nature of the array. By starting with one pointer at the beginning and the other at the end, we can adjust their positions based on the sum of the elements they point to. This allows us to find the pair that adds up to the target without needing to check all possible pairs, which saves time.

By moving the pointers inward, we can systematically find the pair in a single pass through the array. This ensures that the solution is both time-efficient and easy to implement.

Step-by-Step Algorithm

  • Initialize two pointers: Start with one pointer (left) at the beginning (index 0) and the other pointer (right) at the end (last index) of the array.
  • Loop until pointers meet: Continue the loop until left is less than right.
    • Calculate current sum: Add the elements at the left and right pointers.
    • Check if the sum matches the target:
      • If currentSum equals the target sum, return the indices [left, right].
      • If currentSum is less than the target sum, increment the left pointer to increase the sum.
      • If currentSum is more than the target sum, decrement the right pointer to decrease the sum.
  • Return default values: If no pair is found, return [-1, -1].
mediaLink

left = 0 (1), right = 4 (6): sum = 7, which is more than 6, move right back

1 of 4

Code

Here is what our algorithm will look like:

Python3
Python3
. . . .

Time Complexity

  1. Initialization: Constant time, O(1), as it involves assigning values to left and right.

  2. While Loop:

    • The while loop runs as long as left is less than right.
    • In the worst case, this loop iterates over all elements of the array once. This happens when no pair is found, or the pair is found at the extreme ends of the array.
    • Each iteration involves a constant amount of work: calculating currentSum, comparing it with targetSum, and then incrementing left or decrementing right.

    Therefore, the loop runs in O(n) time, where n is the number of elements in the array.

  3. Overall: The dominant factor in this algorithm is the while loop, making the overall time complexity O(n).

Space Complexity

  • The algorithm uses a fixed amount of extra space: variables left, right, and currentSum.
  • It does not depend on the size of the input array, as no additional data structures are used that grow with the input size.
  • Thus, the space complexity is O(1), constant space.

In summary, the algorithm has a time complexity of O(n) and a space complexity of O(1).

An Alternate approach

Instead of using a two-pointer or a binary search approach, we can utilize a HashTable to search for the required pair. We can iterate through the array one number at a time. Let's say during our iteration we are at number X, so we need to find Y such that X + Y == Target. We will do two things here:

Search for Y (which is equivalent to Target - X) in the HashTable. If it is there, we have found the required pair. Otherwise, insert X in the HashTable, so that we can search it for the later numbers.

Step-by-step Algorithm

  1. Initialize a HashMap:

    • Create a HashMap to store numbers as keys and their indices as values.

  2. Iterate through the array:

    • Loop through each element in the array using a for loop.

  3. Check for the complement:

    • For each element, check if the HashMap contains the complement (i.e., targetSum - current element).
    • If it does, return the indices of the complement and the current element.

  4. Store the element and its index:

    • If the complement is not found, store the current element and its index in the HashMap.

  5. Return result:

    • If no pair is found by the end of the loop, return [-1, -1].
mediaLink

i = 0: value 1 needs a complement of 5, which is not in the map yet, so store 1 at index 0.

1 of 4

Code

Python3
Python3
. . . .

Time Complexity

  1. HashMap Initialization: Constant time, O(1).

  2. For Loop:

    • The for loop iterates over each element of the array once.
    • In each iteration, the algorithm checks if the element is already present in the HashMap (or dictionary in Python) and either returns a result or inserts an element into the HashMap.
    • This element checking or insertion operations of a HashMap generally operate in O(1) time due to efficient hashing. However, in the worst case (e.g., when many hash collisions occur), these operations can degrade to O(n). Under the assumption of a good hash function with minimal collisions, these operations can be considered O(1).

    Therefore, the loop runs in O(n) time in the average case, where (n) is the number of elements in the array.

  3. Overall: The dominating factor in this algorithm is the for loop. Under the assumption of efficient hashing, the overall average time complexity is O(n).

Space Complexity

  • The algorithm uses a HashMap to store elements from the array. In the worst case, this map can store all elements of the array if no pair is found that adds up to the target sum
  • Thus, the space complexity is proportional to the number of elements in the array, which is O(n).

In summary, the algorithm has an average time complexity of O(n) and a space complexity of O(n). The time complexity can degrade to O(n^2) in the worst case due to potential hash collisions, but this is generally not the common case with a good hash function.

J

Janarth Kumaresan

· 12 days ago

# Assembly
.global two_sum
.text

# two_sum(const int* arr, size_t n, int target)
#
# Register Mapping (System V ABI):
#   rdi = arr    (pointer to 32-bit signed integers)
#   rsi = n      (length of array)
#   edx = target (32-bit signed integer target sum)
#
# Return Value:
#   rax = combined indices: (left << 32) | (right)
#         Returns -1 (0xFFFFFFFFFFFFFFFF) if no pair exists.

two_sum:
    # 1. Edge case check: if n < 2, return [-1, -1]
    cmp rsi, 2
    jl .not_found

    # 2. Initialize two pointers (indices)
    xor r8, r8          # r8  = left = 0
    mov r9, rsi
    dec r9              # r9  = right = n - 1

.loop:
    # If left >= right, we searched the whole array without finding a pair
    cmp r8, r9
    jge .not_found

    # Load arr[left] and arr[right] (
Show 1 reply
sanjeev saini

sanjeev saini

· 4 months ago

finding a pair only with two pointer approach is basic, but via hashmap we can find multiple pairs too. Even asked in the interview.

public class PairWithTargetSumA1 {

private void search(int[] arr, int targetSum) {
    Map<Integer, Integer> map = new HashMap<>();
    for (int i = 0; i < arr.length; i++) {
        int complement = targetSum - arr[i];
        if (map.containsKey(complement)) {
            System.*out*.println(complement + " " + arr[i]);
        }
        map.put(arr[i], i);
    }
}

public static void main(String[] args) {
    PairWithTargetSumA1 obj = new PairWithTargetSumA1();
    obj.search(new int[] {7, 4, 9, 3, 2, 8, 1}, 10);
}

}

Show 1 reply
Akshay Kumar

Akshay Kumar

· 10 months ago

class Solution:   def search(self, arr, target_sum):     l,r = 0, len(arr)-1     while l<r:       if arr[l]+arr[r]>target_sum:         r-=1       elif arr[l]+arr[r]<target_sum:         l+=1       else:         return l,r     return -1,-1

**InputError 0.093 s Traceback (most recent call last): File "/box/Parsers.py", line 81, in parse return json.loads(line) ^^^^^^^^^^^^^^^^ File "/usr/local/python-3.12.3/lib/python3.12/json/init.py", line 346, in loads return _default_decoder.decode(s) ^^^^^^^^^^^^^^^^^^^^^^^^^^ File "/usr/local/python-3.12.3/lib/python3.12/json/decoder.py", line 337, in decode obj, end = self.raw_decode(s, idx=_w(s, 0).end()) ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ File "/usr/local/python-3.12.3/lib/python3.12/json/decoder.py", line 355, in raw_decode raise JSONDeco

Show 1 reply
Nirav Patel

Nirav Patel

· 2 years ago

For Input Arr = [3,2,4] and targetSum = 6, Expected output = [1,2] But Actual output = [-1, -1].

This is a wrong answer.

Show 3 replies
sealess

sealess

· 3 years ago

class Solution:
  def search(self, arr, target_sum):
    # TODO: Write your code here
    l, r = 0, len(arr) - 1

    while l<r:
      curr= arr[l] + arr[r]
      if curr>target_sum:
        r-=1
      elif curr<target_sum:
        l+=1
      else:
        return [l,r]
    return [-1, -1]
Semih kekül

Semih kekül

· 3 years ago

Question text should say to return -1,-1 when no result exists.

Show 1 reply
C

CaptainKidd

· 4 years ago

FYI if anyone else thinks they're going crazy two-pointer and sliding window have switched spots. I think it's a correct move as sliding window feels like a more specialized version of two-pointer so you get the benefit of general to specifics.

Show 1 reply
D

Deko

· 4 years ago

I think it's important to mention that the solution with a HashMap works even when the array is unsorted.

B

Bryan Pena

· 4 years ago

I keep getting [-1,-1]as the result even though its clear that there is a correct answer from the output

Show 2 replies
O

ornella

· 5 years ago

This one is NOT working on LeetCode. Can someone help me with this please?

Show 4 replies

Reading Progress

0%

Vote for new content

On This Page

Problem Statement

Why this is a Two Pointers problem

Solution

Step-by-Step Algorithm

Code

Time Complexity

Space Complexity

An Alternate approach

Step-by-step Algorithm

Code

Time Complexity

Space Complexity