mediumArraysPattern: Two Pointers
Pair Sum Balance Solution
Problem Statement
Given an array of integers `nums` and a target sum `target`, find all pairs of integers in the array that add up to the target sum, and return the number of pairs where the sum of the indices of the two integers is minimum.
Examples
Example 1:
Input:nums = [1, 3, 5, 7], target = 8
Output:2
Explanation: Pairs (1, 7) and (3, 5) both have a sum of indices 3, with no smaller sum of indices
Example 2:
Input:nums = [2, 4, 6], target = 10
Output:1
Explanation: Only pair (4, 6) adds up to the target sum of 10
Constraints
- 2 <= nums.length <= 10^5
- -10^9 <= nums[i] <= 10^9
- nums contains distinct elements
- -10^9 <= target <= 10^9
- All indices are 0-based
Time: O(n) Space: O(n)
An optimal approach would utilize a hashmap to store the indices of the integers in the array, allowing for constant time lookups and reducing the overall time complexity to O(n). This approach enables efficient tracking of pairs that sum up to the target and their corresponding index sums.
Run, Test & Submit Code
Ready to practice this challenge? Launch our interactive compilation environment with compiler validation.
Solve on Interactive WorkspaceTested Solutions
import sys
t = int(input())
for _ in range(t):
n, target = map(int, input().split())
arr = list(map(int, input().split()))
min_sum = float('inf')
count = 0
for j in range(n):
for k in range(j + 1, n):
if arr[j] + arr[k] == target:
if j + k < min_sum:
min_sum = j + k
count = 1
elif j + k == min_sum:
count += 1
print(count)