In this chapter, we will learn how to solve Pair with Target Sum problem using two pointers technique.
In this chapter, we will learn how to solve Pair with Target Sum problem using two pointers technique.
Given an array, find the maximum sum of any contiguous subarray of size “k” in it.
Example 1:
Input: arr: [2, 6, -9, 7, -1, 5, 4], k: 3
Output: 11
Explanation: The subarray (7, -1, 5) of size 3 gives the maximum sum of 11.
Example 2:
Input: arr: [5, 2, -4, 9, -8, 3, -1, 5], k: 5
Output: 8
Let’s brief the problem first. So, the problem says us to find the sum of each contiguous subarray of size “k” and then take the maximum out of those sum values.
Can you relate this problem with the previous one?
Take a Pause and Think !!!
The brute force approach is quite easy. We can simply calculate the sum of every contiguous subarray of size “k” and take the maximum out of all.
import java.io.*;
class Innoskrit {
public static int maxSumSubarraySumKSize(int arr[], int k) {
int n = arr.length;
int ans = Integer.MIN_VALUE;
for(int i = 0; i < n - k + 1; i++) {
int sum = 0;
for(int j = i; j < i + k; j++) {
sum += arr[j];
}
ans = Math.max(ans, sum);
}
return ans;
}
public static void main (String[] args) {
System.out.println(maxSumSubarraySumKSize(new int[] {2, 6, -9, 7, -1, 5, 4}, 3));
System.out.println(maxSumSubarraySumKSize(new int[] {5, 2, -4, 9, -8, 3, -1, 5}, 5));
}
}
import math
def maxSumSubarraySumKSize(arr, k):
ans = -math.inf
for i in range(len(arr) - k + 1):
sum = 0
for j in range(i, i + k):
sum += arr[j]
ans = max(ans, sum)
return ans
if __name__ == '__main__':
print(maxSumSubarraySumKSize([2, 6, -9, 7, -1, 5, 4], 3))
print(maxSumSubarraySumKSize([5, 2, -4, 9, -8, 3, -1, 5], 5))
#include<bits/stdc++.h>
using namespace std;
class Innoskrit {
public:
static int maxSumSubarraySumKSize(const vector<int>& arr, int k) {
int n = arr.size();
int ans = INT_MIN;
for(int i = 0; i < n - k + 1; i++) {
int sum = 0;
for(int j = i; j < i + k; j++) {
sum += arr[j];
}
ans = std::max(ans, sum);
}
return ans;
}
};
int main(int argc, char * argv[]) {
cout << Innoskrit::maxSumSubarraySumKSize(vector<int>{2, 6, -9, 7, -1, 5, 4}, 3) << endl;
cout << Innoskrit::maxSumSubarraySumKSize(vector<int>{5, 2, -4, 9, -8, 3, -1, 5}, 5);
}
Time Complexity: O(n * k)
This is because for every element in the input array we are calculating the sum of every next k element and then taking max.
Efficient Approach with Sliding Window:
If you will see the above approach carefully you will find out that there is some part that we are repeating in every iteration.
Here is the visual representation of the algorithm.
So, we are treating each contiguous subarray as a sliding window of size k = 3
.
This means when we will move to the next element we will simply slide the window by one element and we will subtract the element going out of the window and add the one which is now newly included in the window.
Our algorithm will look like this:
import java.io.*;
class Innoskrit {
public static int maxSumSubarraySumKSize(int arr[], int k) {
int n = arr.length;
int ans = Integer.MIN_VALUE;
int windowSum = 0;
int windowStart = 0;
for (int windowEnd = 0; windowEnd < n; windowEnd++) {
windowSum += arr[windowEnd];
if(windowEnd >= k - 1) {
ans = Math.max(ans, windowSum);
windowSum -= arr[windowStart];
windowStart++;
}
}
return ans;
}
public static void main (String[] args) {
System.out.println(maxSumSubarraySumKSize(new int[] {2, 6, -9, 7, -1, 5, 4}, 3));
System.out.println(maxSumSubarraySumKSize(new int[] {5, 2, -4, 9, -8, 3, -1, 5}, 5));
}
}
import math
def maxSumSubarraySumKSize(arr, k):
ans = -math.inf
windowSum = 0
windowStart = 0
for windowEnd in range(len(arr)):
windowSum += arr[windowEnd]
if windowEnd >= k - 1:
ans = max(ans, windowSum)
windowSum -= arr[windowStart]
windowStart += 1
return ans
if __name__ == '__main__':
print(maxSumSubarraySumKSize([2, 6, -9, 7, -1, 5, 4], 3))
print(maxSumSubarraySumKSize([5, 2, -4, 9, -8, 3, -1, 5], 5))
#include<bits/stdc++.h>
using namespace std;
class Innoskrit {
public:
static int maxSumSubarraySumKSize(const vector<int>& arr, int k) {
int n = arr.size();
int ans = INT_MIN;
int windowSum = 0;
int windowStart = 0;
for(int windowEnd = 0; windowEnd < n; windowEnd++) {
windowSum += arr[windowEnd];
if(windowEnd >= k - 1) {
ans = std::max(ans, windowSum);
windowSum -= arr[windowStart];
windowStart++;
}
}
return ans;
}
};
int main(int argc, char * argv[]) {
cout << Innoskrit::maxSumSubarraySumKSize(vector<int>{2, 6, -9, 7, -1, 5, 4}, 3) << endl;
cout << Innoskrit::maxSumSubarraySumKSize(vector<int>{5, 2, -4, 9, -8, 3, -1, 5}, 5);
}
Output:
11
8
The time complexity of the above algorithm will be O(N)
, where ‘N’ is the total number of elements in the given array.
The algorithm runs in constant space O(1)
.
© 2022 - All Rights Reserved.