Repository: TheAlgorithms/Java
Pull request #6042 (2024-10-27 14:03:40)

Add Longest Subarray With Sum Less Than or Equal to K algorithm and t…
…ests

<!--
Thank you for your contribution!
In order to reduce the number of notifications sent to the maintainers, please:
- create your PR as draft, cf. https://docs.github.com/en/pull-requests/collaborating-with-pull-requests/proposing-changes-to-your-work-with-pull-requests/about-pull-requests#draft-pull-requests,
- make sure that all of the CI checks pass,
- mark your PR as ready for review, cf. https://docs.github.com/en/pull-requests/collaborating-with-pull-requests/proposing-changes-to-your-work-with-pull-requests/changing-the-stage-of-a-pull-request#marking-a-pull-request-as-ready-for-review
-->

<!-- For completed items, change [ ] to [x] -->

- [x] I have read [CONTRIBUTING.md](https://github.com/TheAlgorithms/Java/blob/master/CONTRIBUTING.md).
- [x] This pull request is all my own work -- I have not plagiarized it.
- [x] All filenames are in PascalCase.
- [x] All functions and variable names follow Java naming conventions.
- [x] All new algorithms have a URL in their comments that points to Wikipedia or other similar explanations.
- [x] All new code is formatted with `clang-format -i --style=file path/to/your/file.java`

codecov-commenter: ## [Codecov](https://app.codecov.io/gh/TheAlgorithms/Java/pull/6042?dropdown=coverage&src=pr&el=h1&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms) Report
Attention: Patch coverage is `90.00000%` with `1 line` in your changes missing coverage. Please review.
> Project coverage is 72.38%. Comparing base [(`a163816`)](https://app.codecov.io/gh/TheAlgorithms/Java/commit/a1638165fead8abf2cab44f6ef58ba5592c4bead?dropdown=coverage&el=desc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms) to head [(`3c9aac6`)](https://app.codecov.io/gh/TheAlgorithms/Java/commit/3c9aac6ec0f4ba204a88537df5560f25e310bc00?dropdown=coverage&el=desc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms).

| [Files with missing lines](https://app.codecov.io/gh/TheAlgorithms/Java/pull/6042?dropdown=coverage&src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms) | Patch % | Lines |
|---|---|---|
| [...ngwindow/LongestSubarrayWithSumLessOrEqualToK.java](https://app.codecov.io/gh/TheAlgorithms/Java/pull/6042?src=pr&el=tree&filepath=src%2Fmain%2Fjava%2Fcom%2Fthealgorithms%2Fslidingwindow%2FLongestSubarrayWithSumLessOrEqualToK.java&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms#diff-c3JjL21haW4vamF2YS9jb20vdGhlYWxnb3JpdGhtcy9zbGlkaW5nd2luZG93L0xvbmdlc3RTdWJhcnJheVdpdGhTdW1MZXNzT3JFcXVhbFRvSy5qYXZh) | 90.00% | [0 Missing and 1 partial :warning: ](https://app.codecov.io/gh/TheAlgorithms/Java/pull/6042?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms) |

<details><summary>Additional details and impacted files</summary>


```diff
@@             Coverage Diff              @@
##             master    #6042      +/-   ##
============================================
+ Coverage     72.37%   72.38%   +0.01%     
- Complexity     4981     4984       +3     
============================================
  Files           652      653       +1     
  Lines         17569    17579      +10     
  Branches       3385     3387       +2     
============================================
+ Hits          12716    12725       +9     
  Misses         4373     4373              
- Partials        480      481       +1     
```

</details>

[:umbrella: View full report in Codecov by Sentry](https://app.codecov.io/gh/TheAlgorithms/Java/pull/6042?dropdown=coverage&src=pr&el=continue&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms).   
:loudspeaker: Have feedback on the report? [Share it here](https://about.codecov.io/codecov-pr-comment-feedback/?utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms).

Chiefpatwal: I have added the Longest Subarray with Sum Less Than or Equal to K algorithm along with its corresponding tests. However, I am encountering issues with the Infer run check, which is failing. I'm currently trying to understand the underlying causes of the failure. Any feedback or guidance would be greatly appreciated!

siriak: The issue with infer is that:
![image](https://github.com/user-attachments/assets/62f56ba4-87fe-4f57-9297-0c737ed8ef64)

siriak: This issue also fails #6009
Chiefpatwal: > This issue also fails #6009

@siriak so clearly this is not my from my end ? besides how can i resolve this conflict...? any suggestions.

siriak: The infer check was fix, update your branch with the latest main and it should be fixed
Chiefpatwal: I have finally resolved the conflicts...already added test you may merge now.
Chiefpatwal: done @siriak 

Patch:
diff --git a/src/main/java/com/thealgorithms/datastructures/trees/BinaryTree.java b/src/main/java/com/thealgorithms/datastructures/trees/BinaryTree.java
index cf0de4a9..ff02fe38 100644
--- a/src/main/java/com/thealgorithms/datastructures/trees/BinaryTree.java
+++ b/src/main/java/com/thealgorithms/datastructures/trees/BinaryTree.java
@@ -144,7 +144,7 @@ public class BinaryTree {
             if (temp == root) {
                 root = null;
             } // This if/else assigns the new node to be either the left or right child of the
-              // parent
+            // parent
             else if (temp.parent.data < temp.data) {
                 temp.parent.right = null;
             } else {
diff --git a/src/main/java/com/thealgorithms/slidingwindow/LongestSubarrayWithSumLessOrEqualToK.java b/src/main/java/com/thealgorithms/slidingwindow/LongestSubarrayWithSumLessOrEqualToK.java
new file mode 100644
index 00000000..55c3f709
--- /dev/null
+++ b/src/main/java/com/thealgorithms/slidingwindow/LongestSubarrayWithSumLessOrEqualToK.java
@@ -0,0 +1,48 @@
+package com.thealgorithms.slidingwindow;
+
+/**
+ * The Longest Subarray with Sum Less Than or Equal to k algorithm finds the length
+ * of the longest subarray whose sum is less than or equal to a given value k.
+ *
+ * <p>
+ * Worst-case performance O(n)
+ * Best-case performance O(n)
+ * Average performance O(n)
+ * Worst-case space complexity O(1)
+ *
+ * @author https://github.com/Chiefpatwal
+ */
+public final class LongestSubarrayWithSumLessOrEqualToK {
+
+    // Prevent instantiation
+    private LongestSubarrayWithSumLessOrEqualToK() {
+    }
+
+    /**
+     * This method finds the length of the longest subarray with a sum less than or equal to k.
+     *
+     * @param arr is the input array
+     * @param k   is the maximum sum allowed
+     * @return the length of the longest subarray with sum less than or equal to k
+     */
+    public static int longestSubarrayWithSumLEK(int[] arr, int k) {
+        int maxLength = 0; // To store the maximum length found
+        int currentSum = 0; // To store the current sum of the window
+        int left = 0; // Left index of the sliding window
+
+        for (int right = 0; right < arr.length; right++) {
+            currentSum += arr[right]; // Expand the window to the right
+
+            // Shrink the window from the left if the current sum exceeds k
+            while (currentSum > k && left <= right) {
+                currentSum -= arr[left]; // Remove the leftmost element
+                left++; // Move the left index to the right
+            }
+
+            // Update maxLength if the current window is valid
+            maxLength = Math.max(maxLength, right - left + 1);
+        }
+
+        return maxLength; // Return the maximum length found
+    }
+}


Test patch:
diff --git a/src/test/java/com/thealgorithms/datastructures/trees/BinaryTreeTest.java b/src/test/java/com/thealgorithms/datastructures/trees/BinaryTreeTest.java
index 08a82e50..d6581fb8 100644
--- a/src/test/java/com/thealgorithms/datastructures/trees/BinaryTreeTest.java
+++ b/src/test/java/com/thealgorithms/datastructures/trees/BinaryTreeTest.java
@@ -1,82 +1,78 @@
 package com.thealgorithms.datastructures.trees;
 
-import static org.junit.jupiter.api.Assertions.assertEquals;
-import static org.junit.jupiter.api.Assertions.fail;
-
+import org.junit.jupiter.api.Assertions;
 import org.junit.jupiter.api.Test;
 
+/**
+ * Unit tests for the BinaryTree class.
+ */
 public class BinaryTreeTest {
 
-    // checks that adding populating the tree and searching for data
-    // retrieves the expected data
     @Test
-    void test1() {
-        BinaryTree t = new BinaryTree();
-        t.put(3);
-        t.put(5);
-        t.put(7);
-        t.put(9);
-        t.put(12);
+    public void testInsertAndFind() {
+        BinaryTree tree = new BinaryTree();
+        tree.put(3);
+        tree.put(5);
+        tree.put(7);
+        tree.put(9);
+        tree.put(12);
 
-        assertEquals(t.find(5).data, 5);
-        assertEquals(t.find(7).data, 7);
+        Assertions.assertNotNull(tree.find(5), "Node with value 5 should exist");
+        Assertions.assertEquals(5, tree.find(5).data, "Value of the found node should be 5");
+        Assertions.assertEquals(7, tree.find(7).data, "Value of the found node should be 7");
     }
 
-    // checks that removing data from the tree
-    // properly removes and makes the new root the expected new root
     @Test
-    void test2() {
-        BinaryTree t = new BinaryTree();
-        t.put(3);
-        t.put(5);
-        t.put(7);
-        t.put(9);
-        t.put(12);
-        t.remove(3);
-        t.remove(5);
-        t.remove(7);
+    public void testRemove() {
+        BinaryTree tree = new BinaryTree();
+        tree.put(3);
+        tree.put(5);
+        tree.put(7);
+        tree.put(9);
+        tree.put(12);
+        tree.remove(3);
+        tree.remove(5);
+        tree.remove(7);
 
-        // Checks whether the root is null before accessing date
-        if (t.getRoot() != null) {
-            assertEquals(t.getRoot().data, 9);
+        Assertions.assertNotNull(tree.getRoot(), "Root should not be null after removals");
+        if (tree.getRoot() != null) {
+            Assertions.assertEquals(9, tree.getRoot().data, "Root value should be 9 after removals");
         } else {
-            fail("The root node is null after removal.");
+            Assertions.fail("Root should not be null after removals, but it is.");
         }
     }
 
-    // checks that removing an unexistend node returns false
-    //  as specified by the documentation of the function
     @Test
-    void test3() {
-        BinaryTree t = new BinaryTree();
-        t.put(3);
-        t.put(5);
-        t.put(7);
-        t.put(9);
-        t.put(12);
+    public void testRemoveReturnValue() {
+        BinaryTree tree = new BinaryTree();
+        tree.put(3);
+        tree.put(5);
+        tree.put(7);
+        tree.put(9);
+        tree.put(12);
 
-        assertEquals(t.remove(9), true);
-        assertEquals(t.remove(398745987), false);
+        Assertions.assertTrue(tree.remove(9), "Removing existing node 9 should return true");
+        Assertions.assertFalse(tree.remove(398745987), "Removing non-existing node should return false");
     }
 
-    // check if the bfs, inOrder, preOrder and postOrder functions
-    // worg as expected, also increases the coverage measures in
-    // JaCoCo
     @Test
-    void test4() {
-        BinaryTree t = new BinaryTree();
-        t.put(3);
-        t.put(5);
-        t.put(7);
-        t.put(9);
-        t.put(12);
+    public void testTraversalMethods() {
+        BinaryTree tree = new BinaryTree();
+        tree.put(3);
+        tree.put(5);
+        tree.put(7);
+        tree.put(9);
+        tree.put(12);
+
+        // Testing traversal methods
+        tree.bfs(tree.getRoot());
+        tree.inOrder(tree.getRoot());
+        tree.preOrder(tree.getRoot());
+        tree.postOrder(tree.getRoot());
 
-        t.bfs(t.find(12));
-        t.inOrder(t.getRoot());
-        t.preOrder(t.getRoot());
-        t.postOrder(t.getRoot());
+        Assertions.assertTrue(tree.remove(9), "Removing existing node 9 should return true");
+        Assertions.assertFalse(tree.remove(398745987), "Removing non-existing node should return false");
 
-        assertEquals(t.remove(9), true);
-        assertEquals(t.remove(398745987), false);
+        Assertions.assertNotNull(tree.getRoot(), "Root should not be null after operations");
     }
 }
diff --git a/src/test/java/com/thealgorithms/slidingwindow/LongestSubarrayWithSumLessOrEqualToKTest.java b/src/test/java/com/thealgorithms/slidingwindow/LongestSubarrayWithSumLessOrEqualToKTest.java
new file mode 100644
index 00000000..da282ab3
--- /dev/null
+++ b/src/test/java/com/thealgorithms/slidingwindow/LongestSubarrayWithSumLessOrEqualToKTest.java
@@ -0,0 +1,22 @@
+package com.thealgorithms.slidingwindow;
+
+import static org.junit.jupiter.api.Assertions.assertEquals;
+
+import org.junit.jupiter.api.Test;
+
+/**
+ * Unit tests for the LongestSubarrayWithSumLessOrEqualToK algorithm.
+ */
+public class LongestSubarrayWithSumLessOrEqualToKTest {
+
+    /**
+     * Tests for the longest subarray with a sum less than or equal to k.
+     */
+    @Test
+    public void testLongestSubarrayWithSumLEK() {
+        assertEquals(3, LongestSubarrayWithSumLessOrEqualToK.longestSubarrayWithSumLEK(new int[] {1, 2, 3, 4}, 6)); // {1, 2, 3}
+        assertEquals(4, LongestSubarrayWithSumLessOrEqualToK.longestSubarrayWithSumLEK(new int[] {1, 2, 3, 4}, 10)); // {1, 2, 3, 4}
+        assertEquals(2, LongestSubarrayWithSumLessOrEqualToK.longestSubarrayWithSumLEK(new int[] {5, 1, 2, 3}, 5)); // {5}
+        assertEquals(0, LongestSubarrayWithSumLessOrEqualToK.longestSubarrayWithSumLEK(new int[] {1, 2, 3}, 0)); // No valid subarray
+    }
+}