Pair Sum - Unsorted

The Budget Buddies problem asks you to find two spending amounts from a list that, when combined, exactly match a given budget. This tests your ability to efficiently search for pairs within a data set, a common task in financial analysis and resource allocation.

arrayhash mapdictionarytwo-sumsearchdata structures

Problem Statement

Given a list of integer expenses and a target budget, find the indices of any two distinct expenses that sum up to the budget. The order of the indices returned does not matter. If no such pair exists, return an empty list.

Example 1

Input: expenses = [5, 8, 1, 9, 2], budget = 10

Output: [0, 4]

expenses[0] + expenses[4] = 5 + 2 = 10. Therefore, the indices 0 and 4 form a valid pair.

Example 2

Input: expenses = [12, 4, 7, 1, 8], budget = 15

Output: [1, 4]

expenses[1] + expenses[4] = 4 + 8 = 15. Therefore, the indices 1 and 4 form a valid pair.

Constraints

-2 <= len(expenses) <= 10^4
-1 <= expenses[i] <= 10^5
-1 <= budget <= 2 * 10^5
-Each expense amount is a non-negative integer.
-You cannot use the same index twice to form the pair.

Brute Force Approach

Imagine you're manually checking every possible combination of expenses against your budget. The brute-force approach is like comparing each expense to every other expense in the list. For each pair, you check if their sum equals the target budget. This involves nested loops, resulting in a time complexity of O(n^2). The space complexity is O(1) since we don't use any extra data structures.

TimeO(n^2)

SpaceO(1)

Ready to practice?

Work through this problem with AI coaching and get real-time feedback

Practice This Problem