Grokking the Coding Interview: Patterns for Coding Questions
Vote

0% completed

​

Pair with Target Sum (easy)

Problem Statement

Try it yourself

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.

Write a function to return the indices of the two numbers (i.e. the pair) such that they add up to the given target. If no such pair exists return [-1, -1].

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>
  • Only one valid answer exists.

Try it yourself

Try solving this question here:

Python3
Python3
. . . .
J

Janarth Kumaresan

· 10 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

Try it yourself