LeetCode Entry
525. Contiguous Array
Max length of subarray sum(0) == sum(1)
525. Contiguous Array medium
blog post
substack
youtube
Join me on Telegram
https://t.me/leetcode_daily_unstoppable/540
Problem TLDR
Max length of subarray sum(0) == sum(1) #medium
Intuition
Let’s observe an example 1 0 1 0 0 1 1 0 0 1 0 0 1 0 1:
// 0 1 2 3 4 5 6 7 8 91011121314
// 1 0 1 0 0 1 1 0 0 1 0 0 1 0 1
// 1 0 1 0-1 0 1 0-1 0-1-2-1-2-1
// * *0 . . . 2
// * *1 . . . 2
// * * * *0. . . 4
// --1 . .
// * * * * * *0 . . 6
// * * * * * *1 . . 6
// * * * * * * * *0 . . 8
// . * * * *-1 . . 4
// * * * * * * * * * *0. . 10
// . * * * * * *-1 . 6
// . --2 .
// . * * * * * * * *-1 . 8
// . * *-2 2
// . * * * * * * * * * *-1 10 = 14 - 4
// 0 1 2 3 4 5 6 7 8 91011121314
Moving the pointer forward and calculating the balance (number of 0 versus number of 1), we can have compute max length up to the current position in O(1). Just store the first encounter of the balance number position.
Approach
Let’s shorten the code with:
- Kotlin:
maxOf,getOrPut - Rust:
max,entry().or_insert
Complexity
-
Time complexity: \(O(n)\)
-
Space complexity: \(O(n)\)
Code
fun findMaxLength(nums: IntArray): Int =
with (mutableMapOf<Int, Int>()) {
put(0, -1); var b = 0
nums.indices.maxOf {
b += if (nums[it] > 0) 1 else -1
it - getOrPut(b) { it }
}
}
pub fn find_max_length(nums: Vec<i32>) -> i32 {
let (mut b, mut bToInd) = (0, HashMap::new());
bToInd.insert(0, -1);
(0..nums.len() as i32).map(|i| {
b += if nums[i as usize] > 0 { 1 } else { -1 };
i - *bToInd.entry(b).or_insert(i)
}).max().unwrap()
}