group men and women

Solution.java

// 1 represents man and -1 represents woman


import java.util.HashMap;

public class Solution {
    /* As we only care about the num of men and women in one group, and based on the fact that they are continuous,
     * we can try add all numbers together with different start point. If at some point we find sum equals to 0,
     * we have found one sub array that has equal number of men and women. The simple method implementation is below.
     * With outer loop defining the start point and inner loop calculating current sum, we can keep looking for sum 0
     * and update the answer.
     * Time complexity is O(n^2)
     * Space complexity is O(1)
     */
    public static int[] longestContinuousNums(int[] nums) {
        int longest = 0;
        int[] res = new int[2];
        for (int i=0; i<nums.length-1; i++) {
            int sum = 0;
            for (int j=i; j<nums.length; j++) {
                sum += nums[j];
                if (sum == 0 && j-i+1 > longest) {
                    res[0] = i;
                    res[1] = j;
                    longest = j - i + 1;
                }
            }
        }

        return res;
    }
    /* A classic approach to achieve better performance is to spend more space to save
     * information we need to speed up the algorithm. With that in mind, and the fact that we use sum
     * to solve this problem in the first method, we can try save all sums from index 0 to i in an array.
     * For example, for array [1, 1, -1, -1, 1, 1, -1, -1, 1, 1], we will have sum array [1, 2, 1, 0, 1, 2, 1, 0, 1, 2]
     * If we observe this sum array, we can find two cases: 1, The current value in sum array is 0,
     * which means from index 0 to current i, we have equal numbers of men and women. However, the start point may not
     * always start at 0, so we have case two. 2, For exmaple, we can focus on "2" in the sum array, because of the sum is calculated
     * from index 0, so if current value in sum array is "2", we want to look for other "2" that appeared before because we can calculate
     * distance based on the position. Because we only care about the longest continuous sub array, we can use greedy algorithm to only save
     * the first appearance position of one sum values. In order to do that, we can intorduce hash map to our algorithm where key is the sum
     * value and value is the index. With the sum array and hash map, we can solve the problem with one loop over sum array.
     * The time complexity is O(n) (n is numer of elements in nums)
     * The space complexity is also O(n)
     */
    public static int[] longestContinuousNums2(int[] nums) {
        int longest = 0;
        int[] res = new int[2];
        if (nums.length == 0) {
            return res;
        }
        int[] sums = new int[nums.length];
        sums[0] = nums[0];
        for (int i=1; i<nums.length; i++) {
            sums[i] = sums[i-1] + nums[i];
        }
        HashMap<Integer, Integer> sumIndex = new HashMap<Integer, Integer>();
        sumIndex.put(0, -1);
        for (int i=0; i<sums.length; i++) {
            int curSum = sums[i];
            if (sumIndex.containsKey(curSum)) {
                int curLength = i - sumIndex.get(curSum);
                if (curLength > longest) {
                    longest = curLength;
                    res[0] = sumIndex.get(curSum) + 1;
                    res[1] = i;
                }
            } else {
                sumIndex.put(curSum, i);
            }
        }

        return res;
    }

    public static void main(String[] args) {
        int[] nums = new int[]{1,1,1,-1,-1,1,1,-1,-1,1};
        int[] res = longestContinuousNums2(nums);
        System.out.println("Range: " + res[0] + " to " + res[1]);
    }
}