C#•7mo ago

Prefix sum with Hashmaps

I'm going through some DSA stuff, and I hit a roadblock on using Prefix Sum with Hashmaps. This is a case of trying to understand by reading other's solutions, but I just can't understand why this works. I don't need to be explained what the code is doing but how the algorithm works. This right here is one of the solutions for 525. Contiguous Array. I'll spoiler mark it just in case.

public class Solution {
    public int FindMaxLength(int[] nums) {
        Dictionary<int, int> counts = new() 
        {
            {0, -1}
        };
        int count = 0;
        int answer = 0;

        for (int i = 0; i < nums.Length; i++)
        {
            if (nums[i] == 1)
                count++;
            else
                count--;
            
            if (counts.ContainsKey(count))
                answer = Math.Max(answer, i - counts[count]);
            else
                counts[count] = i;
        }

        return answer;
    }
}

public class Solution {
    public int FindMaxLength(int[] nums) {
        Dictionary<int, int> counts = new() 
        {
            {0, -1}
        };
        int count = 0;
        int answer = 0;

        for (int i = 0; i < nums.Length; i++)
        {
            if (nums[i] == 1)
                count++;
            else
                count--;
            
            if (counts.ContainsKey(count))
                answer = Math.Max(answer, i - counts[count]);
            else
                counts[count] = i;
        }

        return answer;
    }
}

public class Solution {
    public int FindMaxLength(int[] nums) {
        Dictionary<int, int> counts = new() 
        {
            {0, -1}
        };
        int count = 0;
        int answer = 0;

        for (int i = 0; i < nums.Length; i++)
        {
            if (nums[i] == 1)
                count++;
            else
                count--;
            
            if (counts.ContainsKey(count))
                answer = Math.Max(answer, i - counts[count]);
            else
                counts[count] = i;
        }

        return answer;
    }
}

public class Solution {
    public int FindMaxLength(int[] nums) {
        Dictionary<int, int> counts = new() 
        {
            {0, -1}
        };
        int count = 0;
        int answer = 0;

        for (int i = 0; i < nums.Length; i++)
        {
            if (nums[i] == 1)
                count++;
            else
                count--;
            
            if (counts.ContainsKey(count))
                answer = Math.Max(answer, i - counts[count]);
            else
                counts[count] = i;
        }

        return answer;
    }
}

Prefix sum with Hashmaps

Similar Threads

Similar Threads

Similar Threads