Frontend School

Array Pair Sum: Find Indices for Target Value (Two Sum)

DSA
easy

Array Pair Sum: Find Indices for Target Value (Two Sum)

Easy
Arrays
Hash Table
two-sum
Search
Coding-Interview
practice

Overview

This problem challenges you to find two distinct elements within an array of numbers that sum up to a specific target value. It's a fundamental problem often used to assess basic array manipulation and search techniques. You will return the 0-based indices of these two numbers.

What you need to do / Task

Implement a function findPairSum that takes an array of integers prices and an integer targetBudget. Your task is to:

  1. Find two different indices i and j in the prices array such that prices[i] + prices[j] == targetBudget.
  2. Return these two indices [i, j] as an array of integers.

Input & output

  • prices: An array of integers representing item prices.
  • targetBudget: An integer representing the desired sum.
  • Output: An array of two integers [index1, index2], where index1 and index2 are the 0-based indices of the two numbers that sum to targetBudget. If no such pair exists, return an empty array [].

Clarifications

  • Q: Will there always be exactly one solution? A: No, there might be no solution, or multiple solutions. If multiple solutions exist, any valid pair of indices is acceptable.
  • Q: Can the same element be used twice? A: No, you must use two different elements from the array, meaning index1 must not be equal to index2.
  • Q: What if the input array is empty or contains only one element? A: Such cases will be handled by constraints, but generally, no pair can be formed.
  • Q: What if the target cannot be met? A: If no pair of numbers sums to the target, return an empty array [].

Examples

1

Example 1

Input:

prices = [2, 7, 11, 15], targetBudget = 9

Output:

[0, 1]

Note:

Because prices[0] + prices[1] = 2 + 7 = 9.

2

Example 2

Input:

prices = [3, 2, 4], targetBudget = 6

Output:

[1, 2]

Note:

Because prices[1] + prices[2] = 2 + 4 = 6.

3

Example 3

Input:

prices = [3, 3], targetBudget = 6

Output:

[0, 1]

Note:

Because prices[0] + prices[1] = 3 + 3 = 6. Note that different indices are used even for identical values.

4

Example 4

Input:

prices = [1, 5, 9], targetBudget = 100

Output:

[]

Note:

No two numbers in the array sum up to 100.

Constraints

Constraints & assumptions

  • 2 <= prices.length <= 10^4
  • -10^9 <= prices[i] <= 10^9
  • -10^9 <= targetBudget <= 10^9
  • Each prices[i] is an integer.
  • The same element cannot be used twice.
  • If a solution exists, it is guaranteed to be unique in terms of the values, but there might be multiple pairs of indices that sum to the target if duplicate values are present. Any valid pair of indices is acceptable.

What graders evaluate

  • Correctly identifies two distinct indices whose values sum to the target.
  • Handles cases where no such pair exists by returning an empty array.
  • Provides an efficient solution (e.g., O(n) time complexity).
  • Correctly handles arrays with duplicate numbers and negative numbers.
  • Passes all provided test cases.

Loading editor...