Created
December 3, 2015 03:19
-
-
Save beeflamian/1d0ed028e7c17aaf33c8 to your computer and use it in GitHub Desktop.
group men and women
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
// 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