Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/1983.html

1983. Widest Pair of Indices With Equal Range Sum

Level

Medium

Description

You are given two 0-indexed binary arrays nums1 and nums2. Find the widest pair of indices (i, j) such that i <= j and nums1[i] + nums1[i+1] + ... + nums1[j] == nums2[i] + nums2[i+1] + ... + nums2[j].

The widest pair of indices is the pair with the largest distance between i and j. The distance between a pair of indices is defined as j - i + 1.

Return the distance of the widest pair of indices. If no pair of indices meets the conditions, return 0.

Example 1:

Input: nums1 = [1,1,0,1], nums2 = [0,1,1,0]

Output: 3

Explanation:

If i = 1 and j = 3:

nums1[1] + nums1[2] + nums1[3] = 1 + 0 + 1 = 2.

nums2[1] + nums2[2] + nums2[3] = 1 + 1 + 0 = 2.

The distance between i and j is j - i + 1 = 3 - 1 + 1 = 3.

Example 2:

Input: nums1 = [0,1], nums2 = [1,1]

Output: 1

Explanation:

If i = 1 and j = 1:

nums1[1] = 1.

nums2[1] = 1.

The distance between i and j is j - i + 1 = 1 - 1 + 1 = 1.

Example 3:

Input: nums1 = [0], nums2 = [1]

Output: 0

Explanation:

There are no pairs of indices that meet the requirements.

Constraints:

  • n == nums1.length == nums2.length
  • 1 <= n <= 10^5
  • nums1[i] is either 0 or 1.
  • nums2[i] is either 0 or 1.

Solution

Let differences[i] = nums1[i] - nums2[j]. Then find the widest pair of indices (i, j) such that i <= j and differences[i] + differences[i + 1] + ... + differences[j] == 0. Calculate the prefix sum array of differences and use hash map to store each prefix sum and the smallest index with the prefix sum. For each index j, if there already exists an index i such that the prefix sums at indices i and j are the same, then the width is calculated as j - i. Find the maximum width and return.

  • class Solution {
    public int widestPairOfIndices(int[] nums1, int[] nums2) {
        int length = nums1.length;
        int[] differences = new int[length];
        for (int i = 0; i < length; i++)
            differences[i] = nums1[i] - nums2[i];
        int[] prefixSums = new int[length];
        prefixSums[0] = differences[0];
        for (int i = 1; i < length; i++)
            prefixSums[i] = prefixSums[i - 1] + differences[i];
        int maxDistance = 0;
        Map<Integer, Integer> map = new HashMap<Integer, Integer>();
        map.put(0, -1);
        for (int i = 0; i < length; i++) {
            int sum = prefixSums[i];
            if (map.containsKey(sum))
                maxDistance = Math.max(maxDistance, i - map.get(sum));
            else
                map.put(sum, i);
        }
        return maxDistance;
    }
}

############

class Solution {
    public int widestPairOfIndices(int[] nums1, int[] nums2) {
        Map<Integer, Integer> d = new HashMap<>();
        d.put(0, -1);
        int n = nums1.length;
        int s = 0;
        int ans = 0;
        for (int i = 0; i < n; ++i) {
            s += nums1[i] - nums2[i];
            if (d.containsKey(s)) {
                ans = Math.max(ans, i - d.get(s));
            } else {
                d.put(s, i);
            }
        }
        return ans;
    }
}

  • class Solution {
public:
    int widestPairOfIndices(vector<int>& nums1, vector<int>& nums2) {
        unordered_map<int, int> d;
        d[0] = -1;
        int ans = 0, s = 0;
        int n = nums1.size();
        for (int i = 0; i < n; ++i) {
            s += nums1[i] - nums2[i];
            if (d.count(s)) {
                ans = max(ans, i - d[s]);
            } else {
                d[s] = i;
            }
        }
        return ans;
    }
};

  • class Solution:
    def widestPairOfIndices(self, nums1: List[int], nums2: List[int]) -> int:
        d = {0: -1}
        ans = s = 0
        for i, (a, b) in enumerate(zip(nums1, nums2)):
            s += a - b
            if s in d:
                ans = max(ans, i - d[s])
            else:
                d[s] = i
        return ans


  • func widestPairOfIndices(nums1 []int, nums2 []int) (ans int) {
	d := map[int]int{0: -1}
	s := 0
	for i := range nums1 {
		s += nums1[i] - nums2[i]
		if j, ok := d[s]; ok {
			ans = max(ans, i-j)
		} else {
			d[s] = i
		}
	}
	return
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

All Problems

All Solutions