Skip to content

Commit af80c80

Browse files
Swarga-codesSwarga-codes
authored
Add Sliding Window Problem (TheAlgorithms#4322)
1 parent b61faf4 commit af80c80

File tree

3 files changed

+121
-1
lines changed

3 files changed

+121
-1
lines changed

‎DIRECTORY.md

Lines changed: 19 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -18,6 +18,11 @@
1818
* [Permutation](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/backtracking/Permutation.java)
1919
* [PowerSum](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/backtracking/PowerSum.java)
2020
* [WordSearch](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/backtracking/WordSearch.java)
21+
* bitmanipulation
22+
* [IsEven](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/bitmanipulation/IsEven.java)
23+
* [IsPowerTwo](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/bitmanipulation/IsPowerTwo.java)
24+
* [NumbersDifferentSigns](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/bitmanipulation/NumbersDifferentSigns.java)
25+
* [ReverseBits](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/bitmanipulation/ReverseBits.java)
2126
* ciphers
2227
* a5
2328
* [A5Cipher](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/ciphers/a5/A5Cipher.java)
@@ -128,6 +133,7 @@
128133
* [SearchSinglyLinkedListRecursion](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/datastructures/lists/SearchSinglyLinkedListRecursion.java)
129134
* [SinglyLinkedList](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/datastructures/lists/SinglyLinkedList.java)
130135
* [SkipList](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/datastructures/lists/SkipList.java)
136+
* [Node](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/datastructures/Node.java)
131137
* queues
132138
* [CircularQueue](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/datastructures/queues/CircularQueue.java)
133139
* [Deques](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/datastructures/queues/Deques.java)
@@ -182,7 +188,7 @@
182188
* [TrieImp](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/datastructures/trees/TrieImp.java)
183189
* [VerticalOrderTraversal](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/datastructures/trees/VerticalOrderTraversal.java)
184190
* [ZigzagTraversal](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/datastructures/trees/ZigzagTraversal.java)
185-
* utils
191+
* devutils
186192
* entities
187193
* [ProcessDetails](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/devutils/entities/ProcessDetails.java)
188194
* nodes
@@ -332,6 +338,7 @@
332338
* [SquareRootWithNewtonRaphsonMethod](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/maths/SquareRootWithNewtonRaphsonMethod.java)
333339
* [StandardDeviation](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/maths/StandardDeviation.java)
334340
* [StandardScore](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/maths/StandardScore.java)
341+
* [StrobogrammaticNumber](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/maths/StrobogrammaticNumber.java)
335342
* [SumOfArithmeticSeries](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/maths/SumOfArithmeticSeries.java)
336343
* [SumOfDigits](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/maths/SumOfDigits.java)
337344
* [SumWithoutArithmeticOperators](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/maths/SumWithoutArithmeticOperators.java)
@@ -389,6 +396,7 @@
389396
* [LowestBasePalindrome](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/others/LowestBasePalindrome.java)
390397
* [Luhn](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/others/Luhn.java)
391398
* [Mandelbrot](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/others/Mandelbrot.java)
399+
* [MaximumSumOfDistinctSubarraysWithLengthK](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/others/MaximumSumOfDistinctSubarraysWithLengthK.java)
392400
* [MemoryManagementAlgorithms](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/others/MemoryManagementAlgorithms.java)
393401
* [MiniMaxAlgorithm](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/others/MiniMaxAlgorithm.java)
394402
* [PageRank](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/others/PageRank.java)
@@ -527,6 +535,11 @@
527535
* [PermutationTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/backtracking/PermutationTest.java)
528536
* [PowerSumTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/backtracking/PowerSumTest.java)
529537
* [WordSearchTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/backtracking/WordSearchTest.java)
538+
* bitmanipulation
539+
* [IsEvenTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/bitmanipulation/IsEvenTest.java)
540+
* [IsPowerTwoTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/bitmanipulation/IsPowerTwoTest.java)
541+
* [NumbersDifferentSignsTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/bitmanipulation/NumbersDifferentSignsTest.java)
542+
* [ReverseBitsTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/bitmanipulation/ReverseBitsTest.java)
530543
* ciphers
531544
* a5
532545
* [LFSRTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/ciphers/a5/LFSRTest.java)
@@ -679,6 +692,7 @@
679692
* [SquareRootWithNewtonRaphsonTestMethod](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/maths/SquareRootWithNewtonRaphsonTestMethod.java)
680693
* [StandardDeviationTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/maths/StandardDeviationTest.java)
681694
* [StandardScoreTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/maths/StandardScoreTest.java)
695+
* [StrobogrammaticNumberTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/maths/StrobogrammaticNumberTest.java)
682696
* [SumOfArithmeticSeriesTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/maths/SumOfArithmeticSeriesTest.java)
683697
* [SumOfDigitsTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/maths/SumOfDigitsTest.java)
684698
* [SumWithoutArithmeticOperatorsTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/maths/SumWithoutArithmeticOperatorsTest.java)
@@ -704,6 +718,7 @@
704718
* [LineSweepTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/others/LineSweepTest.java)
705719
* [LinkListSortTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/others/LinkListSortTest.java)
706720
* [LowestBasePalindromeTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/others/LowestBasePalindromeTest.java)
721+
* [MaximumSumOfDistinctSubarraysWithLengthKTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/others/MaximumSumOfDistinctSubarraysWithLengthKTest.java)
707722
* [NewManShanksPrimeTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/others/NewManShanksPrimeTest.java)
708723
* [NextFitTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/others/NextFitTest.java)
709724
* [PasswordGenTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/others/PasswordGenTest.java)
@@ -720,6 +735,7 @@
720735
* searches
721736
* [BinarySearch2dArrayTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/searches/BinarySearch2dArrayTest.java)
722737
* [BreadthFirstSearchTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/searches/BreadthFirstSearchTest.java)
738+
* [DepthFirstSearchTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/searches/DepthFirstSearchTest.java)
723739
* [HowManyTimesRotatedTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/searches/HowManyTimesRotatedTest.java)
724740
* [KMPSearchTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/searches/KMPSearchTest.java)
725741
* [OrderAgnosticBinarySearchTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/searches/OrderAgnosticBinarySearchTest.java)
@@ -738,12 +754,14 @@
738754
* [CombSortTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/sorts/CombSortTest.java)
739755
* [DualPivotQuickSortTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/sorts/DualPivotQuickSortTest.java)
740756
* [DutchNationalFlagSortTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/sorts/DutchNationalFlagSortTest.java)
757+
* [GnomeSortTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/sorts/GnomeSortTest.java)
741758
* [HeapSortTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/sorts/HeapSortTest.java)
742759
* [InsertionSortTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/sorts/InsertionSortTest.java)
743760
* [IntrospectiveSortTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/sorts/IntrospectiveSortTest.java)
744761
* [MergeSortRecursiveTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/sorts/MergeSortRecursiveTest.java)
745762
* [MergeSortTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/sorts/MergeSortTest.java)
746763
* [OddEvenSortTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/sorts/OddEvenSortTest.java)
764+
* [PancakeSortTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/sorts/PancakeSortTest.java)
747765
* [QuickSortTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/sorts/QuickSortTest.java)
748766
* [SelectionSortTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/sorts/SelectionSortTest.java)
749767
* [ShellSortTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/sorts/ShellSortTest.java)

‎src/main/java/com/thealgorithms/others/MaximumSumOfDistinctSubarraysWithLengthK.java

Lines changed: 70 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,70 @@
1+
package com.thealgorithms.others;
2+
3+
import java.util.HashSet;
4+
5+
/*
6+
References: https://en.wikipedia.org/wiki/Streaming_algorithm
7+
* In this model, the function of interest is computing over a fixed-size window in the stream. As the stream progresses,
8+
* items from the end of the window are removed from consideration while new items from the stream take their place.
9+
* @author Swarga-codes (https://github.com/Swarga-codes)
10+
*/
11+
public class MaximumSumOfDistinctSubarraysWithLengthK {
12+
/*
13+
* Returns the maximum sum of subarray of size K consisting of distinct
14+
* elements.
15+
*
16+
* @param k size of the subarray which should be considered from the given
17+
* array.
18+
*
19+
* @param nums is the array from which we would be finding the required
20+
* subarray.
21+
*
22+
* @return the maximum sum of distinct subarray of size K.
23+
*/
24+
public static long maximumSubarraySum(int k, int... nums) {
25+
if (nums.length < k) return 0;
26+
long max = 0; // this will store the max sum which will be our result
27+
long s = 0; // this will store the sum of every k elements which can be used to compare with
28+
// max
29+
HashSet<Integer> set = new HashSet<>(); // this can be used to store unique elements in our subarray
30+
// Looping through k elements to get the sum of first k elements
31+
for (int i = 0; i < k; i++) {
32+
s += nums[i];
33+
set.add(nums[i]);
34+
}
35+
// Checking if the first kth subarray contains unique elements or not if so then
36+
// we assign that to max
37+
if (set.size() == k) {
38+
max = s;
39+
}
40+
// Looping through the rest of the array to find different subarrays and also
41+
// utilising the sliding window algorithm to find the sum
42+
// in O(n) time complexity
43+
for (int i = 1; i < nums.length - k + 1; i++) {
44+
s = s - nums[i - 1];
45+
s = s + nums[i + k - 1];
46+
int j = i;
47+
boolean flag = false; // flag value which says that the subarray contains distinct elements
48+
while (j < i + k && set.size() < k) {
49+
if (nums[i - 1] == nums[j]) {
50+
flag = true;
51+
break;
52+
} else {
53+
j++;
54+
}
55+
}
56+
if (!flag) {
57+
set.remove(nums[i - 1]);
58+
}
59+
set.add(nums[i + k - 1]);
60+
// if the subarray contains distinct elements then we compare and update the max
61+
// value
62+
if (set.size() == k) {
63+
if (max < s) {
64+
max = s;
65+
}
66+
}
67+
}
68+
return max; // the final maximum sum
69+
}
70+
}

‎src/test/java/com/thealgorithms/others/MaximumSumOfDistinctSubarraysWithLengthKTest.java

Lines changed: 32 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,32 @@
1+
package com.thealgorithms.others;
2+
3+
import static org.junit.jupiter.api.Assertions.*;
4+
5+
import org.junit.jupiter.api.Test;
6+
7+
public class MaximumSumOfDistinctSubarraysWithLengthKTest {
8+
@Test
9+
public void SampleTestCase1() {
10+
assertEquals(15, MaximumSumOfDistinctSubarraysWithLengthK.maximumSubarraySum(3, 1, 5, 4, 2, 9, 9, 9));
11+
}
12+
13+
@Test
14+
public void SampleTestCase2() {
15+
assertEquals(0, MaximumSumOfDistinctSubarraysWithLengthK.maximumSubarraySum(3, 4, 4, 4));
16+
}
17+
18+
@Test
19+
public void SampleTestCase3() {
20+
assertEquals(12, MaximumSumOfDistinctSubarraysWithLengthK.maximumSubarraySum(3, 9, 9, 9, 1, 2, 3));
21+
}
22+
23+
@Test
24+
public void EdgeCase1() {
25+
assertEquals(0, MaximumSumOfDistinctSubarraysWithLengthK.maximumSubarraySum(0, 9, 9, 9));
26+
}
27+
28+
@Test
29+
public void EdgeCase2() {
30+
assertEquals(0, MaximumSumOfDistinctSubarraysWithLengthK.maximumSubarraySum(5, 9, 9, 9));
31+
}
32+
}

0 commit comments

Comments
 (0)