Eddy
BAN USERActually there is a much more simple solution to this problem: all you need to do is to take the array elements from the end and add them to each bucket, then after you finished adding an element to each bucket you continue but reverse the bucket order, so now you will add to the last bucket you added, repeat until you reach the end of the array. Tested on multiple inputs including: [-1, 1, 1, 1, 10, 8 ], K = 2 and [1,3,6,9,10], k= 3 java code is bellow, sorry for variable naming and any language mistakes,time complexity O(n), space: O(n) (for storing the buckets)
public static void solve(ArrayList<Integer> array, int k) {
int maxBucketSize = (int) Math.ceil((double) array.size() / k);
int[][] buckets = new int[k][maxBucketSize];
int i = array.size() - 1;
int counter = 0;
boolean addToLastBucketFirst = false;
while (i >= 0) {
if (!addToLastBucketFirst) {
// add elements in the bucket order
for (int j = 0; j < k; j++) {
buckets[j][counter] = array.get(i);
i--;
if (i < 0) {
break;
}
}
addToLastBucketFirst = true;
counter++;
} else {
// add elements in reverse bucket order
for (int j = k - 1; j >= 0; j--) {
buckets[j][counter] = array.get(i);
i--;
if (i < 0) {
break;
}
}
addToLastBucketFirst = false;
counter++;
}
}
// Print buckets
for (i = 0; i < k; i++) {
for (int j = 0; j < buckets[i].length; j++) {
System.out.print(buckets[i][j] + " ");
}
System.out.println();
}
}
"1. Start from top right corner.
2. Go left if it has 1 on its left, down otherwise
3. We find the longest 1 sequence in O(m+n).
We keep count of the longest sequence.
Reiterate over the collumn where the longest ends
And print the row info if it has a 1 on that position."
Your answer is good but I think it is incomplete, what if the last row in the example matrix had one more 1, the sequence you found in step 3 might not be the longest, one fix could be to iterate over the column where the current longest sequence begins and try to reapply steps 1 and 2. You must also keep track of the current max length and the position of the row that you found it and if there are no more rows to reapply steps 1 and 2 then you know you got the longest sequence and you can start printing the positions. I think the complexity should stay the same.
One solution could be to iterate the array and make a sum (we'll call it currentSum) as you go. As long as currentSum + currentNumber >= 0 you keep adding the numbers to the currentSum, else you store the current sum in a maxSum variable if currentSum >maxSum and set you currentSum to 0 and continue with the next element in the array. Also to be able to print the subArray you would have to store the beginning and the end indexes of the subArray, so every time you begin a new currentSum you store the beginning index and then when you replace the maxSum with currentSum you have your end index, you store them as maxStartIndex and maxEndIndex or something. Then to print the subArray you just loop from maxStartIndex to maxEndIndex. I hope my explanation is understandable.
- Eddy May 04, 2017