Frontend School

Find Pair for Target Sum in Sorted Array

DSA
easy

Find Pair for Target Sum in Sorted Array

Easy
Arrays
Two Pointers
sorted-array

Overview

At Groww, we process vast amounts of financial data daily. Efficiently searching and correlating data points is crucial for many services, from transaction analysis to risk assessment. Imagine you have a sorted list of values representing financial metrics, and you need to quickly identify if any two of these values sum up to a specific target. This problem challenges your ability to leverage the sorted nature of data to find such pairs optimally.

What you need to do / Task

You are given a 0-indexed array of integers numbers that is sorted in non-decreasing order. Your task is to find two distinct indices, index1 and index2 (where index1 < index2), such that numbers[index1] + numbers[index2] equals a given target number.

You must return the indices of these two numbers as an integer array [index1, index2]. Remember that the problem expects the indices to be 1-indexed.

Input & Output

Input

  • numbers: An array of integers, sorted in non-decreasing order.
  • target: An integer representing the sum we are looking for.

Output

  • An array of two integers [index1, index2], representing the 1-indexed positions of the two numbers that sum up to target.

Clarifications

  • There is exactly one solution.
  • You may not use the same element twice. This means index1 must be different from index2.
  • The output indices index1 and index2 must be 1-indexed.

Examples

1

Example 1

Input:

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

Output:

[1,2]

Note:

Because numbers[0] (2) + numbers[1] (7) == 9, we return the 1-indexed positions [1, 2].

2

Example 2

Input:

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

Output:

[1,3]

Note:

Because numbers[0] (2) + numbers[2] (4) == 6, we return the 1-indexed positions [1, 3].

3

Example 3

Input:

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

Output:

[1,2]

Note:

Because numbers[0] (-1) + numbers[1] (0) == -1, we return the 1-indexed positions [1, 2].

Constraints

Constraints & Assumptions

  • 2 <= numbers.length <= 3 * 10^4
  • -1000 <= numbers[i] <= 1000
  • numbers is sorted in non-decreasing order.
  • -1000 <= target <= 1000
  • The tests are generated such that there is exactly one solution.
  • You may not use the same element twice (i.e., the two indices must be distinct).

What interviewers evaluate

  • Correctness: Does the code produce the correct 1-indexed pair for all valid inputs, including edge cases?
  • Efficiency: Is the solution optimal in terms of time and space complexity, leveraging the sorted input? (Expected: O(N) time, O(1) space).
  • Readability & Maintainability: Is the code clean, well-structured, and easy to understand?
  • Problem-Solving Approach: Did the candidate articulate a clear thought process, consider alternatives, and justify their chosen approach?

Loading editor...