1983. Widest Pair of Indices With Equal Range Sum
Problem Description
In this problem, we have two binary arrays nums1
and nums2
. Both arrays are of the same length and contain only 0s and 1s. Our goal is to find the widest pair of indices (i, j)
that satisfy two conditions:
i
must be less than or equal toj
, and- The sum of elements from
i
toj
innums1
must be equal to the sum of elements fromi
toj
innums2
.
The concept of the "widest" pair refers to the pair (i, j)
with the biggest difference between i
and j
. This means that we are looking for the longest subarray where the sums of nums1
and nums2
are equal. The "distance" indicates the number of elements in this subarray, which is calculated as j - i + 1
.
We need to return the "distance" of the widest pair of indices. If no pairs meet the condition, we should return 0.
Intuition
To find the solution, we use the cumulative sums of both arrays and keep track of their differences at each index. If the difference between the sums of subarrays from nums1
and nums2
up to the current index i
has been seen before at some index j
, then the subarrays from j+1
to i
in both nums1
and nums2
must be equal.
Here are the steps to solve this problem:
-
Maintain a dictionary
d
to store the first occurrence of each cumulative sum difference with its index. Initialize this dictionary with{0: -1}
, meaning that if the difference is 0 at index 0, it can be considered as a subarray starting from index 0. -
Iterate through the two arrays
nums1
andnums2
simultaneously usingenumerate(zip(nums1, nums2))
to get both the index and the elements. -
Calculate the cumulative difference
s
by subtracting the element ofnums2
from the element ofnums1
and adding it to the previous cumulative difference. -
Check if this difference
s
has occurred before by looking it up in the dictionaryd
. If it exists, it means that there is a subarray that starts from the stored index plus 1 and ends at the current indexi
which has equal sums innums1
andnums2
. Updateans
with the maximum distance found so far, which isi - d[s]
. -
If the difference
s
does not exist in the dictionary, it means this is the first time we've seen this cumulative sum difference, so we add the current indexi
to the dictionary with the key being the sum differences
. -
After traversing through the whole arrays, the variable
ans
will contain the distance of the widest pair of indices. Returnans
.
Learn more about Prefix Sum patterns.
Solution Approach
The solution to this problem utilizes a dictionary data structure for efficient lookups and an iterative approach to find the widest pair where the subarrays have equal sums. Here's a deep dive into how the Solution
class implements this:
-
Dictionary for Cumulative Difference Tracking:
- The dictionary
d
is used to store cumulative sum differences as keys and their first occurring indices as values. It's initialized with{0: -1}
to handle cases where the subarray starts from the first element.
- The dictionary
-
Running Sum Difference Calculation:
- As we loop through each element of both arrays, we calculate a running sum difference
s
by addingnums1[i] - nums2[i]
to the current sum difference. This represents the difference between the cumulative sums up to the current indexi
.
- As we loop through each element of both arrays, we calculate a running sum difference
-
Lookup and Widest Pair Tracking:
- During each iteration, we check if the current sum difference
s
is found in dictionaryd
.- If it exists, it indicates we have previously seen this sum difference at an earlier index, meaning the sums of subarrays from the previous index to the current index in both
nums1
andnums2
are equal. - The distance of the current widest pair is calculated by subtracting the earlier index where the sum difference was the same from the current index, i.e.,
i - d[s]
. - We update
ans
to the maximum of the current distance and the existing widest distance found so far.
- If it exists, it indicates we have previously seen this sum difference at an earlier index, meaning the sums of subarrays from the previous index to the current index in both
- If the sum difference
s
is not found ind
, it implies this difference is encountered the first time at indexi
, so we adds
as a key tod
with the current indexi
as its value. This will potentially serve as the starting index for a future widest pair.
- During each iteration, we check if the current sum difference
-
Returning the Result:
- After the loop is completed,
ans
holds the distance of the widest pair found. This value is returned as the output of the function.
- After the loop is completed,
The algorithm's complexity is primarily dictated by the single traversal of the input arrays, leading to an overall time complexity of O(n) where n is the number of elements in the input arrays. The space complexity is O(k), where k is the number of unique sum differences, which can be at most n in the worst case.
The solution is efficient because it avoids nested loops by using the cumulative sum difference, which allows us to identify equal sum subarrays in linear time.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's walk through a small example to illustrate the solution approach using two binary arrays nums1
and nums2
.
Initial State:
- Let
nums1 = [1, 0, 0, 1]
andnums2 = [0, 1, 1, 0]
. - Initialize the dictionary
d
with{0: -1}
to handle the case where the sum difference starts from index 0.
Step-by-Step Solution:
-
Start iterating over both arrays. Initialize a variable
s
to keep track of the cumulative sum difference, andans
to store the maximum width found so far. -
Iteration 0: The elements at index 0 are
nums1[0] = 1
andnums2[0] = 0
.- The sum difference
s
becomes1 - 0 = 1
. - This difference is not in
d
, so we add it:d[1] = 0
.
- The sum difference
-
Iteration 1: The elements at index 1 are
nums1[1] = 0
andnums2[1] = 1
.- The sum difference
s
becomes1 + (0 - 1) = 0
, which is already ind
. - The width between
d[0] + 1 = 0
and index 1 is1 - 0 + 1 = 2
. - Update
ans
to 2.
- The sum difference
-
Iteration 2: The elements at index 2 are
nums1[2] = 0
andnums2[2] = 1
.- The sum difference
s
remains0
(since0 - 0 + 0 - 1 = -1
and we add this to the previouss
which was1
, making the news
back to0
). - We have already seen
0
ind
. - The width is
2 - (-1) + 1 = 4
. - Update
ans
to 4, since this is larger than the previous value ofans
.
- The sum difference
-
Iteration 3: The elements at index 3 are
nums1[3] = 1
andnums2[3] = 0
.- The sum difference
s
becomes0 + (1 - 0) = 1
, which is already ind
. - We do not update
ans
because the current distance3 - d[1] = 3
is not greater than the currentans
(which is 4).
- The sum difference
-
After traversing all items,
ans
is 4, which represents the distance of the widest pair of indices where the sum of elements innums1
is equal to the sum of elements innums2
.
The solution finds the widest subarray efficiently, utilizing a dictionary to track the first occurrence of each cumulative sum difference and iterating over the arrays only once.
Solution Implementation
1class Solution:
2 def widestPairOfIndices(self, nums1: List[int], nums2: List[int]) -> int:
3 # Initialize a dictionary to store the first occurrence of a
4 # particular prefix sum difference. The sum difference is initialized
5 # with a base case: 0 sum difference occurs at index -1.
6 index_map = {0: -1}
7
8 # Initialize variable to track the maximum width
9 max_width = 0
10
11 # Initialize a prefix sum difference variable
12 sum_diff = 0
13
14 # Loop through each pair of values from the two lists
15 for index, (value1, value2) in enumerate(zip(nums1, nums2)):
16 # Update the running sum difference with the difference of the current pair
17 sum_diff += value1 - value2
18
19 # If the sum difference has been seen before, calculate the width
20 if sum_diff in index_map:
21 # The width is the current index minus the index where the same
22 # sum difference was first recorded
23 width = index - index_map[sum_diff]
24 # Update the maximum width if this width is greater
25 max_width = max(max_width, width)
26 else:
27 # Otherwise, record the first occurrence of this sum difference
28 index_map[sum_diff] = index
29
30 # Return the maximum width found
31 return max_width
32
1class Solution {
2 public int widestPairOfIndices(int[] nums1, int[] nums2) {
3 // HashMap to store the first occurrence of the sum difference 'sumDiff' as a key and its index as the value.
4 Map<Integer, Integer> firstOccurrenceMap = new HashMap<>();
5 firstOccurrenceMap.put(0, -1); // Initialize with sumDiff 0 occurring before the array starts.
6
7 int arrayLength = nums1.length; // Length of the input arrays.
8 int sumDiff = 0; // Variable to keep track of the cumulative sum difference between nums1 and nums2.
9 int maxDistance = 0; // Variable to store the maximum distance (widest pair) found.
10
11 // Iterate over the elements of the input arrays.
12 for (int i = 0; i < arrayLength; ++i) {
13 // Calculate the cumulative sum difference at current index.
14 sumDiff += nums1[i] - nums2[i];
15
16 // Check if the cumulative sum difference has been seen before.
17 if (firstOccurrenceMap.containsKey(sumDiff)) {
18 // If seen before, calculate the distance and update the maximum distance if current is greater.
19 maxDistance = Math.max(maxDistance, i - firstOccurrenceMap.get(sumDiff));
20 } else {
21 // If not seen before, record the first occurrence of this sum difference with its index.
22 firstOccurrenceMap.put(sumDiff, i);
23 }
24 }
25
26 // Return the maximum distance found (the widest pair of indices).
27 return maxDistance;
28 }
29}
30
1class Solution {
2public:
3 // Function to calculate the widest pair of indices where the sum of subarrays are equal
4 int widestPairOfIndices(vector<int>& nums1, vector<int>& nums2) {
5 unordered_map<int, int> prefixSums; // Maps prefix sum difference to the earliest index
6 prefixSums[0] = -1; // Initialize with 0 difference at index -1
7 int maxWidth = 0; // To store the maximum width
8 int prefixSumDifference = 0; // To store the running difference of prefix sums
9 int length = nums1.size(); // Length of the input arrays
10
11 // Iterate over the array elements
12 for (int i = 0; i < length; ++i) {
13 // Update the running difference between nums1 and nums2 at index i
14 prefixSumDifference += nums1[i] - nums2[i];
15
16 // If this difference has been seen before, calculate width
17 if (prefixSums.count(prefixSumDifference)) {
18 // Update maxWidth if we found a wider pair
19 maxWidth = max(maxWidth, i - prefixSums[prefixSumDifference]);
20 } else {
21 // Else, store the current index for this difference
22 prefixSums[prefixSumDifference] = i;
23 }
24 }
25 // Return the maximum width found
26 return maxWidth;
27 }
28};
29
1// Importing necessary utility
2import { max } from "lodash";
3
4// Function to calculate the widest pair of indices where the sum of subarrays are equal
5function widestPairOfIndices(nums1: number[], nums2: number[]): number {
6 let prefixSums: { [key: number]: number } = {}; // Maps prefix sum difference to the earliest index
7 prefixSums[0] = -1; // Initialize with 0 difference at index -1
8 let maxWidth = 0; // To store the maximum width
9 let prefixSumDifference = 0; // To store the running difference of prefix sums
10 let length = nums1.length; // Length of the input arrays
11
12 // Iterate over the array elements
13 for (let i = 0; i < length; i++) {
14 // Update the running difference between nums1 and nums2 at index i
15 prefixSumDifference += nums1[i] - nums2[i];
16
17 // If this difference has been seen before, calculate width
18 if (prefixSumDifference in prefixSums) {
19 // Update maxWidth if we found a wider pair
20 maxWidth = max([maxWidth, i - prefixSums[prefixSumDifference]])!;
21 } else {
22 // Else, store the current index for this difference
23 prefixSums[prefixSumDifference] = i;
24 }
25 }
26 // Return the maximum width found
27 return maxWidth;
28}
29
Time and Space Complexity
The given Python function widestPairOfIndices
seeks to find the widest pair of indices (i, j)
such that sum(nums1[k]) for k in range(0, i + 1)
is equal to sum(nums2[k]) for k in range(0, i + 1)
. It accomplishes this by using a dictionary d
to keep track of the differences between the prefixes of the two lists and when each difference was first seen.
Time Complexity:
The time complexity of the function can be analyzed as follows:
- There is a single loop that iterates over the elements of
nums1
andnums2
, which both have the same length, sayn
. - Within each iteration, the function performs constant-time operations: a calculation involving
a
andb
, anif
condition check, a dictionary lookup, and an update to the dictionary (which on average is constant time for a hash table) and variable for the answerans
. - These operations within the loop are conducted in constant time, regardless of the size of the input.
As the loop runs n
times where n
is the length of the input lists, and each iteration is done in constant time, the time complexity of the function is O(n)
.
Space Complexity:
The space complexity of the function depends on the auxiliary space used, which is mainly for storing the dictionary d
:
- In the worst-case scenario, the dictionary could store a distinct entry for each element in the input lists if all prefix sums were unique. Thus, in the worst case, it could have up to
n
entries. - Aside from this, the space used by variables
s
andans
is constant, as well as a few other intermediate variables.
Therefore, the worst-case space complexity is O(n)
where n
is the length of the input lists.
Learn more about how to find time and space complexity quickly using problem constraints.
A heap is a ...?
Recommended Readings
Prefix Sum The prefix sum is an incredibly powerful and straightforward technique Its primary goal is to allow for constant time range sum queries on an array What is Prefix Sum The prefix sum of an array at index i is the sum of all numbers from index 0 to i By
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Want a Structured Path to Master System Design Too? Donāt Miss This!