Skip to content

Added the Sliding Window problem and removed all the conflicts as it had before #4322

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Merged
merged 7 commits into from
Aug 18, 2023
+121 −1
Merged

Added the Sliding Window problem and removed all the conflicts as it had before #4322

Show file tree
Hide file tree
Changes from all commits
Commits
Show all changes
7 commits
Select commit Hold shift + click to select a range
dc0f826
Update directory
Aug 17, 2023
825f74d
added maximum sum of distinct subarrays with length K (sliding window…
Swarga-codes Aug 17, 2023
ea497b5
Update directory
Aug 17, 2023
067dfaf
added clang formatting
Swarga-codes Aug 18, 2023
d13e2b1
Merge branch 'master' of https://github.com/Swarga-codes/Java
Swarga-codes Aug 18, 2023
b05ebca
Merge branch 'master' into master
siriak Aug 18, 2023
682dc13
Update directory
Aug 18, 2023
File filter

Filter by extension

Filter by extension
Conversations
Failed to load comments.
Loading
Jump to
Jump to file
Failed to load files.
Loading
Diff view
Diff view
20 changes: 19 additions & 1 deletion DIRECTORY.md
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -18,6 +18,11 @@
* [Permutation](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/backtracking/Permutation.java)
* [PowerSum](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/backtracking/PowerSum.java)
* [WordSearch](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/backtracking/WordSearch.java)
* bitmanipulation
* [IsEven](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/bitmanipulation/IsEven.java)
* [IsPowerTwo](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/bitmanipulation/IsPowerTwo.java)
* [NumbersDifferentSigns](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/bitmanipulation/NumbersDifferentSigns.java)
* [ReverseBits](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/bitmanipulation/ReverseBits.java)
* ciphers
* a5
* [A5Cipher](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/ciphers/a5/A5Cipher.java)
Expand Down Expand Up @@ -128,6 +133,7 @@
* [SearchSinglyLinkedListRecursion](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/datastructures/lists/SearchSinglyLinkedListRecursion.java)
* [SinglyLinkedList](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/datastructures/lists/SinglyLinkedList.java)
* [SkipList](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/datastructures/lists/SkipList.java)
* [Node](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/datastructures/Node.java)
* queues
* [CircularQueue](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/datastructures/queues/CircularQueue.java)
* [Deques](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/datastructures/queues/Deques.java)
Expand Down Expand Up @@ -182,7 +188,7 @@
* [TrieImp](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/datastructures/trees/TrieImp.java)
* [VerticalOrderTraversal](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/datastructures/trees/VerticalOrderTraversal.java)
* [ZigzagTraversal](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/datastructures/trees/ZigzagTraversal.java)
* utils
* devutils
* entities
* [ProcessDetails](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/devutils/entities/ProcessDetails.java)
* nodes
Expand Down Expand Up @@ -332,6 +338,7 @@
* [SquareRootWithNewtonRaphsonMethod](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/maths/SquareRootWithNewtonRaphsonMethod.java)
* [StandardDeviation](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/maths/StandardDeviation.java)
* [StandardScore](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/maths/StandardScore.java)
* [StrobogrammaticNumber](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/maths/StrobogrammaticNumber.java)
* [SumOfArithmeticSeries](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/maths/SumOfArithmeticSeries.java)
* [SumOfDigits](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/maths/SumOfDigits.java)
* [SumWithoutArithmeticOperators](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/maths/SumWithoutArithmeticOperators.java)
Expand Down Expand Up @@ -389,6 +396,7 @@
* [LowestBasePalindrome](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/others/LowestBasePalindrome.java)
* [Luhn](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/others/Luhn.java)
* [Mandelbrot](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/others/Mandelbrot.java)
* [MaximumSumOfDistinctSubarraysWithLengthK](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/others/MaximumSumOfDistinctSubarraysWithLengthK.java)
* [MemoryManagementAlgorithms](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/others/MemoryManagementAlgorithms.java)
* [MiniMaxAlgorithm](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/others/MiniMaxAlgorithm.java)
* [PageRank](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/others/PageRank.java)
Expand Down Expand Up @@ -527,6 +535,11 @@
* [PermutationTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/backtracking/PermutationTest.java)
* [PowerSumTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/backtracking/PowerSumTest.java)
* [WordSearchTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/backtracking/WordSearchTest.java)
* bitmanipulation
* [IsEvenTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/bitmanipulation/IsEvenTest.java)
* [IsPowerTwoTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/bitmanipulation/IsPowerTwoTest.java)
* [NumbersDifferentSignsTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/bitmanipulation/NumbersDifferentSignsTest.java)
* [ReverseBitsTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/bitmanipulation/ReverseBitsTest.java)
* ciphers
* a5
* [LFSRTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/ciphers/a5/LFSRTest.java)
Expand Down Expand Up @@ -679,6 +692,7 @@
* [SquareRootWithNewtonRaphsonTestMethod](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/maths/SquareRootWithNewtonRaphsonTestMethod.java)
* [StandardDeviationTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/maths/StandardDeviationTest.java)
* [StandardScoreTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/maths/StandardScoreTest.java)
* [StrobogrammaticNumberTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/maths/StrobogrammaticNumberTest.java)
* [SumOfArithmeticSeriesTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/maths/SumOfArithmeticSeriesTest.java)
* [SumOfDigitsTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/maths/SumOfDigitsTest.java)
* [SumWithoutArithmeticOperatorsTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/maths/SumWithoutArithmeticOperatorsTest.java)
Expand All @@ -704,6 +718,7 @@
* [LineSweepTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/others/LineSweepTest.java)
* [LinkListSortTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/others/LinkListSortTest.java)
* [LowestBasePalindromeTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/others/LowestBasePalindromeTest.java)
* [MaximumSumOfDistinctSubarraysWithLengthKTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/others/MaximumSumOfDistinctSubarraysWithLengthKTest.java)
* [NewManShanksPrimeTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/others/NewManShanksPrimeTest.java)
* [NextFitTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/others/NextFitTest.java)
* [PasswordGenTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/others/PasswordGenTest.java)
Expand All @@ -720,6 +735,7 @@
* searches
* [BinarySearch2dArrayTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/searches/BinarySearch2dArrayTest.java)
* [BreadthFirstSearchTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/searches/BreadthFirstSearchTest.java)
* [DepthFirstSearchTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/searches/DepthFirstSearchTest.java)
* [HowManyTimesRotatedTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/searches/HowManyTimesRotatedTest.java)
* [KMPSearchTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/searches/KMPSearchTest.java)
* [OrderAgnosticBinarySearchTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/searches/OrderAgnosticBinarySearchTest.java)
Expand All @@ -738,12 +754,14 @@
* [CombSortTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/sorts/CombSortTest.java)
* [DualPivotQuickSortTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/sorts/DualPivotQuickSortTest.java)
* [DutchNationalFlagSortTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/sorts/DutchNationalFlagSortTest.java)
* [GnomeSortTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/sorts/GnomeSortTest.java)
* [HeapSortTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/sorts/HeapSortTest.java)
* [InsertionSortTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/sorts/InsertionSortTest.java)
* [IntrospectiveSortTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/sorts/IntrospectiveSortTest.java)
* [MergeSortRecursiveTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/sorts/MergeSortRecursiveTest.java)
* [MergeSortTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/sorts/MergeSortTest.java)
* [OddEvenSortTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/sorts/OddEvenSortTest.java)
* [PancakeSortTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/sorts/PancakeSortTest.java)
* [QuickSortTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/sorts/QuickSortTest.java)
* [SelectionSortTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/sorts/SelectionSortTest.java)
* [ShellSortTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/sorts/ShellSortTest.java)
Expand Down
70 changes: 70 additions & 0 deletions src/main/java/com/thealgorithms/others/MaximumSumOfDistinctSubarraysWithLengthK.java
View file
Open in desktop
Original file line number Diff line number Diff line change
@@ -0,0 +1,70 @@
package com.thealgorithms.others;

import java.util.HashSet;

/*
References: https://en.wikipedia.org/wiki/Streaming_algorithm
* In this model, the function of interest is computing over a fixed-size window in the stream. As the stream progresses,
* items from the end of the window are removed from consideration while new items from the stream take their place.
* @author Swarga-codes (https://github.com/Swarga-codes)
*/
public class MaximumSumOfDistinctSubarraysWithLengthK {
/*
* Returns the maximum sum of subarray of size K consisting of distinct
* elements.
*
* @param k size of the subarray which should be considered from the given
* array.
*
* @param nums is the array from which we would be finding the required
* subarray.
*
* @return the maximum sum of distinct subarray of size K.
*/
public static long maximumSubarraySum(int k, int... nums) {
if (nums.length < k) return 0;
long max = 0; // this will store the max sum which will be our result
long s = 0; // this will store the sum of every k elements which can be used to compare with
// max
HashSet<Integer> set = new HashSet<>(); // this can be used to store unique elements in our subarray
// Looping through k elements to get the sum of first k elements
for (int i = 0; i < k; i++) {
s += nums[i];
set.add(nums[i]);
}
// Checking if the first kth subarray contains unique elements or not if so then
// we assign that to max
if (set.size() == k) {
max = s;
}
// Looping through the rest of the array to find different subarrays and also
// utilising the sliding window algorithm to find the sum
// in O(n) time complexity
for (int i = 1; i < nums.length - k + 1; i++) {
s = s - nums[i - 1];
s = s + nums[i + k - 1];
int j = i;
boolean flag = false; // flag value which says that the subarray contains distinct elements
while (j < i + k && set.size() < k) {
if (nums[i - 1] == nums[j]) {
flag = true;
break;
} else {
j++;
}
}
if (!flag) {
set.remove(nums[i - 1]);
}
set.add(nums[i + k - 1]);
// if the subarray contains distinct elements then we compare and update the max
// value
if (set.size() == k) {
if (max < s) {
max = s;
}
}
}
return max; // the final maximum sum
}
}
32 changes: 32 additions & 0 deletions src/test/java/com/thealgorithms/others/MaximumSumOfDistinctSubarraysWithLengthKTest.java
View file
Open in desktop
Original file line number Diff line number Diff line change
@@ -0,0 +1,32 @@
package com.thealgorithms.others;

import static org.junit.jupiter.api.Assertions.*;

import org.junit.jupiter.api.Test;

public class MaximumSumOfDistinctSubarraysWithLengthKTest {
@Test
public void SampleTestCase1() {
assertEquals(15, MaximumSumOfDistinctSubarraysWithLengthK.maximumSubarraySum(3, 1, 5, 4, 2, 9, 9, 9));
}

@Test
public void SampleTestCase2() {
assertEquals(0, MaximumSumOfDistinctSubarraysWithLengthK.maximumSubarraySum(3, 4, 4, 4));
}

@Test
public void SampleTestCase3() {
assertEquals(12, MaximumSumOfDistinctSubarraysWithLengthK.maximumSubarraySum(3, 9, 9, 9, 1, 2, 3));
}

@Test
public void EdgeCase1() {
assertEquals(0, MaximumSumOfDistinctSubarraysWithLengthK.maximumSubarraySum(0, 9, 9, 9));
}

@Test
public void EdgeCase2() {
assertEquals(0, MaximumSumOfDistinctSubarraysWithLengthK.maximumSubarraySum(5, 9, 9, 9));
}
}