GreatestSubArray
The Problem Statement
Given an array arr[] of integers and an integer K, the task is to find the greatest contiguous sub-array of size K. Sub-array X is said to be greater than sub-array Y if the first non-matching element in both the sub-arrays has a greater value in X than in Y.
Sample Input & Output
Input: arr[] = {1, 4, 3, 2, 5}, K = 4
Output: 4 3 2 5
Two subarrays are {1, 4, 3, 2} and {4, 3, 2, 5}.
Hence, the greater one is {4, 3, 2, 5}
Input: arr[] = {1, 9, 2, 7, 9, 3}, K = 3
Output: 9 2 7
Input: arr[] = {1, 4, 3, 2, 5}, K = 4
Output: 4 3 2 5
Two subarrays are {1, 4, 3, 2} and {4, 3, 2, 5}.
Hence, the greater one is {4, 3, 2, 5}
Two subarrays are {1, 4, 3, 2} and {4, 3, 2, 5}.
Hence, the greater one is {4, 3, 2, 5}
Input: arr[] = {1, 9, 2, 7, 9, 3}, K = 3
Output: 9 2 7
Output: 9 2 7
Naive Algorithm
For each element in the array of size n , you can form a pair with next "k" elements and preserve it if it is highest till now . Repeat this till you have reached end ( or rather you have reached "n-k"th element). The efficiency of this algorithm is O(n*k) as you are iterating to k elements for each elements of array of size n. We are using an extra temporary int element.
Efficient Algorithm
If you think carefully, you can see that , we need to form subarrays as we walk and then find the subarray with highest sum. If you think further, there will be only "n-k+1" number of subarrays. The time efficiency is O(n).
To bring more improvement from space point of view, we really dont need to store the individual arrays. We can just store the sum of K elements in a new Single Array. But the problem is we are summing the elements as we walk through , not all at once so the sum is built gradually . So how do we know where we keep intermediate sum and where we add next element to.
We really don't need to , let's see this with example.
arr[] = {1, 4, 3, 2, 5}, K = 4
We would have n -k +1 = 5 -4 +1 = 2
So we would have SumArray of Size 2 , index 0 & index 1.
sumArray[0] = 1 + 4 + 3+2 = 10
sumArray[1] = 4+3 +2 +5 = 14
How do you build it?
sumArray[index] = arr[index] + arr[index+1]+ ........+ arr[index+k-1]
Of course, you will have to handle conditions.
private static int[] getSumArrays(int[] input, int k) {
int[] sumArray = new int[input.length - k + 1];
for (int i = 0; i < input.length; i++) {
for (int j = 0; j < k; j++) {
if (i - j >= 0 && i - j < sumArray.length)
sumArray[i - j] += input[i];
}
}
return sumArray;
}
You can find complete code here at Github.
* Courtesy : geeksforgeeks.org
If you think carefully, you can see that , we need to form subarrays as we walk and then find the subarray with highest sum. If you think further, there will be only "n-k+1" number of subarrays. The time efficiency is O(n).
To bring more improvement from space point of view, we really dont need to store the individual arrays. We can just store the sum of K elements in a new Single Array. But the problem is we are summing the elements as we walk through , not all at once so the sum is built gradually . So how do we know where we keep intermediate sum and where we add next element to.
We really don't need to , let's see this with example.
arr[] = {1, 4, 3, 2, 5}, K = 4
We would have n -k +1 = 5 -4 +1 = 2
So we would have SumArray of Size 2 , index 0 & index 1.
sumArray[0] = 1 + 4 + 3+2 = 10
sumArray[1] = 4+3 +2 +5 = 14
How do you build it?
sumArray[index] = arr[index] + arr[index+1]+ ........+ arr[index+k-1]
Of course, you will have to handle conditions.
private static int[] getSumArrays(int[] input, int k) {
int[] sumArray = new int[input.length - k + 1];
for (int i = 0; i < input.length; i++) {
for (int j = 0; j < k; j++) {
if (i - j >= 0 && i - j < sumArray.length)
sumArray[i - j] += input[i];
}
}
return sumArray;
}
You can find complete code here at Github.
* Courtesy : geeksforgeeks.org
No comments:
Post a Comment