Skip to content

Instantly share code, notes, and snippets.

@beeflamian
Created December 3, 2015 03:19
Show Gist options
  • Save beeflamian/1d0ed028e7c17aaf33c8 to your computer and use it in GitHub Desktop.
Save beeflamian/1d0ed028e7c17aaf33c8 to your computer and use it in GitHub Desktop.
group men and women
// 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]);
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment