Frontend School

Find Pair with Target Sum in Sorted Array

DSA
easy

Find Pair with Target Sum in Sorted Array

Easy
Two Pointers
Arrays
Search

Overview

At Meesho, efficiently processing order batches and identifying complementary product bundles is crucial for optimizing logistics and customer experience. Imagine we have a list of product prices, already sorted to streamline inventory management. We need a quick way to identify two specific products whose prices sum up to a target value, perhaps for a special bundled offer or to detect pricing anomalies.

What you need to do / Task

You are given a 0-indexed integer array numbers that is sorted in non-decreasing order. Your task is to find two numbers in this array such that they add up to a specific target number. Return the 1-based indices of these two numbers as an integer array [index1, index2], where index1 < index2.

You are guaranteed that there is exactly one solution. You may not use the same element twice.

Input & output

  • Input:
    • numbers: An array of integers, sorted in non-decreasing order.
    • target: An integer representing the desired sum.
  • Output:
    • An array of two integers [index1, index2], representing the 1-based indices of the two numbers in numbers that sum up to target. index1 must be less than index2.

Clarifications

  • The input array numbers will always be sorted in non-decreasing order.
  • There will always be exactly one pair of numbers that sum up to target.
  • You cannot use the same element twice (e.g., numbers[i] and numbers[i]). The two indices must be distinct.

Examples

1

Example 1

Input:

numbers = [2,7,11,15], target = 9

Output:

[1,2]

Note:

The numbers at 0-indexed positions 0 (value 2) and 1 (value 7) sum up to 9. Since we need 1-based indices, we return [1,2].

2

Example 2

Input:

numbers = [2,3,4], target = 6

Output:

[2,3]

Note:

The numbers at 0-indexed positions 1 (value 3) and 2 (value 4) sum up to 6. In 1-based indices, this is [2,3].

3

Example 3

Input:

numbers = [-1,0], target = -1

Output:

[1,2]

Note:

The numbers at 0-indexed positions 0 (value -1) and 1 (value 0) sum up to -1. In 1-based indices, this is [1,2].

Constraints

Constraints & assumptions

  • 2 <= numbers.length <= 10^4
  • -1000 <= numbers[i] <= 1000
  • -1000 <= target <= 1000
  • The numbers in numbers are sorted in non-decreasing order.
  • There is exactly one solution.
  • You must use O(1) extra space.

Out of scope

  • Handling unsorted input arrays (assume the input is always sorted).
  • Returning all possible pairs if multiple solutions existed (only one is guaranteed).
  • Extensive error handling for invalid input types or ranges beyond the specified constraints.

What interviewers evaluate

  • Correctness: Does the solution produce the correct output for all valid inputs?
  • Efficiency: Is the solution optimal in terms of time and space complexity? (Expected: O(N) time, O(1) space).
  • Code Quality: Is the code clean, readable, and well-structured?
  • Edge Cases: Does the solution correctly handle minimum/maximum array sizes and values?

Loading editor...