easyArraysPattern: Two Pointers

CombinedSizePairs Solution

Problem Statement

Given a sorted array of integers `nums` in non-decreasing order, return the total number of index pairs `(i, j)` such that `0 <= i < j < nums.length` and `nums[i] + nums[j] == 27`.

Examples

Example 1:

Input:nums = [10, 12, 15, 17, 20]

Output:undefined

Explanation: The only pair of indices is (0, 3) which corresponds to values 10 + 17 = 27.

Example 2:

Input:nums = [8, 13, 14, 14, 20]

Output:undefined

Explanation: There are two valid pairs of indices: (1, 2) and (1, 3), both resulting in 13 + 14 = 27.

Constraints

0 <= nums.length <= 10^5
-10^9 <= nums[i] <= 10^9
nums is sorted in non-decreasing order.

Time: O(N) Space: O(1)

Since the array is already sorted, we can use a two-pointer technique with pointers starting at the beginning and the end of the array. We move the pointers inward based on whether the current sum is smaller or larger than 27, taking care to handle duplicate elements when counting matches. This allows us to find all valid index pairs in a single linear pass.

Step-by-Step dry run

i=0: num=1, cur=1, max=1 i=1: num=1, cur=2, max=2 i=2: num=0, cur=0, max=2 i=3: num=1, cur=1, max=2 i=4: num=1, cur=2, max=2 i=5: num=1, cur=3, max=3

Run, Test & Submit Code

Ready to practice this challenge? Launch our interactive compilation environment with compiler validation.

Solve on Interactive Workspace

Tested Solutions

import sys

def solve():
    try:
        input_data = sys.stdin.read().replace('[', '').replace(']', '').replace(',', ' ').split()
    except Exception:
        print(0)
        return
    
    if not input_data:
        print(0)
        return
        
    nums = []
    for x in input_data:
        try:
            nums.append(int(x))
        except ValueError:
            continue
            
    ans = 0
    L = 0
    R = len(nums) - 1
    
    while L < R:
        s = nums[L] + nums[R]
        if s < 27:
            L += 1
        elif s > 27:
            R -= 1
        else:
            if nums[L] == nums[R]:
                count = R - L + 1
                ans += count * (count - 1) // 2
                break
            else:
                countL = 1
                while L + 1 < R and nums[L] == nums[L+1]:
                    countL += 1
                    L += 1
                countR = 1
                while R - 1 > L and nums[R] == nums[R-1]:
                    countR += 1
                    R -= 1
                ans += countL * countR
                L += 1
                R -= 1
    print(ans)

if __name__ == '__main__':
    solve()