702693. Perfect Array
Perfect Array
Slug: perfect-array2344 Difficulty: Basic Id: 702693 Topic Tags: Arrays, Data Structures Company Tags: None
Summary
The Perfect Array problem involves given an array and a target sum. The task is to find the number of pairs in the array that add up to the target sum.
Detailed Explanation
One approach to solve this problem is by using two pointers technique. Initialize two pointers, one at the start and one at the end of the array. Compare the sum of the values at these positions with the target sum. If the sum is equal to the target sum, increment a counter for the pair found. Move the pointer that points to the smaller value towards the other pointer. Repeat this process until the pointers meet.
Time complexity: O(n log n) due to sorting Space complexity: O(1) as we are not using any extra space
Here is an example of how this approach works:
[1, 2, 3, 4, 5] (original array)
^ ^
| |
start end
________________________
| 1 | 2 | 3 | 4 | 5 |
|-----|-----|-----|-----|-----|
0 1 2 3 4 5
The pointers start at the beginning and end of the array, respectively. The sum of the values at these positions is 1 + 5 = 6, which is greater than the target sum. So, we move the pointer that points to the smaller value (1) towards the other pointer (5). Repeat this process until the pointers meet.
Optimized Solutions
Java
public int findPairs(int[] arr, int targetSum) {
Arrays.sort(arr);
int count = 0;
int start = 0;
int end = arr.length - 1;
while (start < end) {
if (arr[start] + arr[end] == targetSum) {
count++;
start++;
end--;
} else if (arr[start] + arr[end] < targetSum) {
start++;
} else {
end--;
}
}
return count;
}