Leetcode 525. Contiguous Array (Typescript)

With several hable table problems under our belt, lets do a slightly more difficult problem with Leetcode 525 - Contiguous Array.

Problem statement and analysis

The problem statement is as follows:

Given a binary array nums, return the maximum length of a contiguous subarray with an equal number of 0 and 1.

So I am going to be honest with the reader. This problem threw me for a loop initially. I knew that the primary tool to consider here is yet again a hash table. But honesty I did not have a great idea of how one might be used. I considered a two pointer approach where I essentially would keep track of the start index of a candidate continuous subarray and then keep iterating until my other pointer found the end of the nums. The max contiguous length would be whather the largest delta I calculated was between pointers. But that just seemed a big complicated.

Then I thought about some of our recent work with prefix sums. And then I thought of the classic Leetcode 1 - Two Sum problem. We calculated a sum of sorts each iteration as we ran through elements. And then we stored differences and effectively their index in a hash table. While it's not quite applicable we can actually still use a similar approach.

1. Let's go ahead and keep a running sum going. This running sum will represent prefix sums up to a certain index num in the nums array. Or in other words it will be the cumulative sum of the nums array up to that index. (more on that in point two).
2. We are going to then consider every 0 in the array to be a -1 instead. Why on earth do we do this? Well if you think about it, every time we find a 1 in the array we can consider that "increasing" the sum so far of values calculated. The more positive this number becomes the further away we are getting from having parity with an equal amount of offsetting 0's and thus forming a contiguous subarray. As we find 0's it's like we should subtract values from the running sum because it represents us getting closer to parity. Now honestly this designation is completely arbitrary. We could have just as easily designated 1's as -1's and 0's as +1's. But the important thing is that we are going to be using this designation to calculate a running sum.
3. Each number in the loop we are going to calculte the latest running sum (add or subtract 1). We then are going to check whether the running sum exists as a key in our hash table (more on this in a bit). If we find the value in the hash table this is great! what it means is we essentially have said "hey every up to that index we found doesnt matter". It's as if we have collapsed all those values previous to that index value to a singular prefix sum. Then the delta between the index in which we've found the match and our current index is a subarray of equal 0's and 1's. We then assign this as the new longest contiguous length if it is greater than the previous longest contiguous length.
4. If we dont find this running sum in our hash table that means we have no new continuous subarray to calculate. We add a key of the running sum and the index to our hash table to use in future iterations.
5. Finally we return the longest contiguous length.

Now, one key this we haven't covered above. If our continuous subarray starts at the beginning of the nums array we will never find a match in our hash table. So we need to add a key of 0 and a value of -1 to our hash table. This of this as a "dummy" key that tells our algorithm "hey before index 0, the sum of the array is 0". If this is confusing thats okay it took me quite a bit to understand it as well. Let me see if a simple example will help. Say we have:

const nums = [0, 1];

1. At index 0, we have a running sum of -1 (0-1). We add this to our hash table with a value of 0. So our hash table looks like this:

{
    -1: 0
}

2. At index 1, we have a running sum of 0 (-1+1). We check our hash table and find that we do not have a match! So we add the key of 0 and value of 1 to our hash table. So our hash table looks like this:

{
    -1: 0,
    0: 1
}

So accoring to our loop we never found a continuous subarray! But we know that obvious 0 and 1 form a contiguous subarray of length 2. Now let's add back in that dummy key/value pair and recalculate index 1

{
    0: -1
    -1: 0,
}

Hey now we have pair 0,-1 ahead of time. So if we calculate the delta we have (1-(-1) = 2). So we have a contiguous subarray of length 2. Hopefully this helps explain why we need the dummy key a bit better.

With all of that explanation out of the way, let's look at one more example to help solidify the concept.

const nums = [0, 1, 0, 1, 0, 1];

Here's a table showing the step-by-step execution for the example:

Result: The maximum length of a contiguous subarray with equal 0s and 1s is 6.

With two example out of the way, lets finally take a look at my solution:

Solution

function findMaxLength(nums: number[]): number {
  const numMap = new Map<number, number>([[0, -1]]);
  let runningSum = 0;
  let maxContiguousLen = 0;

  for (const [idx, num] of nums.entries()) {
    runningSum += num === 0 ? -1 : 1;
    if (numMap.has(runningSum)) {
      maxContiguousLen = Math.max(
        maxContiguousLen,
        idx - numMap.get(runningSum)
      );
    } else {
      numMap.set(runningSum, idx);
    }
  }

  return maxContiguousLen;
}

Time and Space Complexity

The time complexity of this problem is O(N) because we must iterate through the entire array once. The space complexity is also O(N) because we are storing the running sum and its corresponding index in a hash table. If you think about it our worst case could be that the array contains all 0's or all 1's. In this case we would have to store nums.length entries in our hash table.

Thanks and best of luck on your algorithmic journey!