# C++ O(N), array instead of unordered_map.

• This is the same as "325. Maximum Size Subarray Sum Equals k" (https://leetcode.com/problems/maximum-size-subarray-sum-equals-k/), where zeros are -1, ones are ones, and k is zero. Since in this problem the range of possible sums is [-size...size], we can use an array instead of unordered_map. We can consider size as the zero point, so the array indexes will be [0... 2 * size].

``````int findMaxLength(vector<int>& nums) {
int size = nums.size(), ballance = size, max_len = 0;
int ballances[size * 2 + 1] = {};
for (auto i = 0; i < size; ++i) {
ballance += nums[i] == 0 ? -1 : 1;
if (ballance == size) max_len = i + 1;
else {
if (ballances[ballance] != 0) max_len = max(max_len, i - ballances[ballance] + 1);
else ballances[ballance] = i + 1;
}
}
return max_len;
}
``````

• Could define perfect balance as `ballance == size`, then you wouldn't need the `+ size`.

• @StefanPochmann Cool, updated the code and description.

• This post is deleted!

• ``````if (ballances[ballance] != 0)
max_len = max(max_len, i - ballances[ballance] + 1);
else
ballances[ballance] = i + 1;
``````

if you write

``````ballances[ballance] = i;
``````

it should be okay

``````max_len = max(max_len, i - ballances[ballance]);
``````

• @wdw828
you can do it, but you should initialize the ballances like
vector<int> ballances(size*2+1,-1);

• C# - I ran both to see if this was significant. And the OJ results are so inconsistent that it was hard to say for sure, although it did seem the array version was slightly faster. The array version has to be faster but also uses more memory so not sure overall which is better.

``````    public int FindMaxLength(int[] nums)
{
int[] map = new int[2 * (nums.Length + 1)];
int mid = map.Length / 2;

int max = 0;
int delta = 0;
for (int i = 0; i < nums.Length; i++)
{
delta += nums[i] == 0 ? -1 : 1;
if (delta == 0)
{
max = i + 1;
}
else if (map[mid + delta] == 0)
{
map[mid + delta] = i + 1; // use 0 as not-set
}
else if (max < i + 1 - map[mid + delta])
{
max = i + 1 - map[mid + delta];
}
}
return max;
}
``````

with Map

``````    public int FindMaxLength(int[] nums)
{
Dictionary<int,int> map = new Dictionary<int,int>();

int max = 0;
int delta = 0;
for (int i = 0; i < nums.Length; i++)
{
delta += nums[i] == 0 ? -1 : 1;
if (delta == 0)
{
max = i + 1;
}
else if (!map.ContainsKey(delta))
{
map[delta] = i;
}
else if (max < i - map[delta])
{
max = i - map[delta];
}
}
return max;
}
``````

• This post is deleted!

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.