easyTwo PointersPattern: Opposite Pointers
Parity-Based Pointer Convergence Solution
Problem Statement
You are given an array of integers nums. You place two pointers, left at the start of the array (index 0) and right at the end of the array (index nums.length - 1). You move the pointers inward according to the following rules until they meet (i.e., left == right): 1. If the sum of the elements at the current pointer positions (nums[left] + nums[right]) is even, increment the left pointer by 1. 2. If the sum is odd, decrement the right pointer by 1. Return the index at which the two pointers meet.
Examples
Example 1:
Input:nums = [1, 2, 4, 6, 7]
Output:3
Explanation: Start with left = 0 (value 1) and right = 4 (value 7). The sum is 1 + 7 = 8 (even), so increment left to 1. Next, left = 1 (value 2) and right = 4 (value 7). The sum is 2 + 7 = 9 (odd), so decrement right to 3. Next, left = 1 (value 2) and right = 3 (value 6). The sum is 2 + 6 = 8 (even), so increment left to 2. Next, left = 2 (value 4) and right = 3 (value 6). The sum is 4 + 6 = 10 (even), so increment left to 3. Now left and right meet at index 3.
Example 2:
Input:nums = [3, 5, 8, 2]
Output:1
Explanation: Start with left = 0 (value 3) and right = 3 (value 2). The sum is 3 + 2 = 5 (odd), so decrement right to 2. Next, left = 0 (value 3) and right = 2 (value 8). The sum is 3 + 8 = 11 (odd), so decrement right to 1. Next, left = 0 (value 3) and right = 1 (value 5). The sum is 3 + 5 = 8 (even), so increment left to 1. Now left and right meet at index 1.
Constraints
- 1 <= nums.length <= 10^5
- -10^9 <= nums[i] <= 10^9
Time: O(n) Space: O(1)
The optimal approach directly simulates the pointer convergence using the two-pointer technique. We initialize two pointers at both ends of the array and repeatedly calculate their sum, moving either the left or right pointer inward depending on the parity of the sum until they meet. This guarantees finding the meeting point in exactly N - 1 steps.
Run, Test & Submit Code
Ready to practice this challenge? Launch our interactive compilation environment with compiler validation.
Solve on Interactive WorkspaceTested Solutions
No solution code is currently loaded.
Complete this code in the workspace editor.