Subarrays having sum less than K

Given an array arr[] of non-negative numbers and a non-negative number k, find the number of subarrays having sum less than k. We may assume that there is no overflow.

Examples :  

Input: arr[] = [2, 5, 6], K = 10
Output: 4
Explanation: The subarrays are [2], [5], [6], and [2, 5]

Input: arr[] = [1, 11, 2, 3, 15], K = 10
Output: 4
Explanation: The subarrays are [1], [2], [3], and [2, 3]

Naive Approach - O(n²) Time and O(1) Space

Check every possible subarray and compute its sum. For each starting index, extend the subarray one element at a time and count it if the sum is less than K. Stop extending when the sum becomes greater than or equal to K since it will only increase further.

Steps:

• Run a loop from 0 to n-1 to select the starting index of the subarray
• For each starting index, run another loop from i to n-1 to select the ending index
• Maintain a variable sum to store the current subarray sum
• Add elements one by one to sum
• If sum < K, increment the count
• If sum ≥ K, break the inner loop (since all elements are non-negative) 

#include <vector>
using namespace std;

// Function to count subarrays having sum less than k
int countsubarray(vector<int> &arr, int k)
{
    int n = arr.size();
    int count = 0;

    // Pick starting point
    for (int i = 0; i < n; i++)
    {
        int sum = 0;

        // Pick ending point
        for (int j = i; j < n; j++)
        {
            // If sum is less than k, update sum and count
            if (sum + arr[j] < k)
            {
                sum += arr[j];
                count++;
            }
            else
            {
                break;
            }
        }
    }

    return count;
}

int main()
{
    vector<int> arr = {1, 11, 2, 3, 15};
    int k = 10;

    cout << countsubarray(arr, k);

    return 0;
}

class GFG {

    // Function to count subarrays having sum less than k
    static int countsubarray(int[] arr, int k)
    {
        int n = arr.length;
        int count = 0;

        // Pick starting point
        for (int i = 0; i < n; i++) {
            int sum = 0;

            // Pick ending point
            for (int j = i; j < n; j++) {
                // If sum is less than k, update sum and
                // count
                if (sum + arr[j] < k) {
                    sum += arr[j];
                    count++;
                }
                else {
                    break;
                }
            }
        }

        return count;
    }

    public static void main(String[] args)
    {
        int[] arr = { 1, 11, 2, 3, 15 };
        int k = 10;

        System.out.println(countsubarray(arr, k));
    }
}

def countsubarray(arr, k):

    n = len(arr)
    count = 0

    # Pick starting point
    for i in range(n):
        sum = 0

        # Pick ending point
        for j in range(i, n):

            # If sum is less than k, update sum and count
            if sum + arr[j] < k:
                sum += arr[j]
                count += 1
            else:
                break

    return count


if __name__ == "__main__":
    arr = [1, 11, 2, 3, 15]
    k = 10

    print(countsubarray(arr, k))

using System;

class GFG {
    // Function to count subarrays having sum less than k
    public static int countsubarray(int[] arr, int k)
    {
        int n = arr.Length;
        int count = 0;

        // Pick starting point
        for (int i = 0; i < n; i++) {
            int sum = 0;

            // Pick ending point
            for (int j = i; j < n; j++) {
                // If sum is less than k, update sum and
                // count
                if (sum + arr[j] < k) {
                    sum += arr[j];
                    count++;
                }
                else {
                    break;
                }
            }
        }

        return count;
    }

    static void Main()
    {
        int[] arr = { 1, 11, 2, 3, 15 };
        int k = 10;

        Console.WriteLine(countsubarray(arr, k));
    }
}

// Function to count subarrays having sum less than k
function countsubarray(arr, k)
{
    let n = arr.length;
    let count = 0;

    // Pick starting point
    for (let i = 0; i < n; i++) {
        let sum = 0;

        // Pick ending point
        for (let j = i; j < n; j++) {
            // If sum is less than k, update sum and count
            if (sum + arr[j] < k) {
                sum += arr[j];
                count++;
            }
            else {
                break;
            }
        }
    }

    return count;
}

// driver code
let arr = [ 1, 11, 2, 3, 15 ];
let k = 10;

console.log(countsubarray(arr, k));

4

Sliding Window - O(n) Time and O(1) Space

The idea of this approach is to use two pointers, start and end, to form a window (subarray). This window expands when we move end forward and shrinks when we move start forward, so that the sum of elements inside the window always remains less than K.

Steps

• Start with start = 0, sum = 0, and count = 0
• Move end step by step and keep adding the current element to sum
• If the sum becomes equal to or greater than K, remove elements from the beginning by subtracting arr[start] and moving start forward
• Keep removing elements until the sum becomes less than K again
• Now the current window has sum less than K
• Count all subarrays that end at end by adding (end - start + 1) to count

#include <vector>
using namespace std;

// Function to count subarrays having sum less than k
int countsubarray(vector<int> &arr, int k)
{
    int n = arr.size();
    int start = 0;
    int sum = 0;
    int count = 0;

    // Move end pointer
    for (int end = 0; end < n; end++)
    {
        sum += arr[end];

        // If sum becomes too large, shrink the window
        while (sum >= k)
        {
            sum -= arr[start];
            start++;
        }

        // Count valid subarrays ending at end
        count += (end - start + 1);
    }

    return count;
}

int main()
{
    vector<int> arr = {1, 11, 2, 3, 15};
    int k = 10;

    cout << countsubarray(arr, k);

    return 0;
}

class GFG {

    // Function to count subarrays having sum less than k
    static int countsubarray(int[] arr, int k)
    {
        int n = arr.length;
        int start = 0;
        int sum = 0;
        int count = 0;

        // Move end pointer
        for (int end = 0; end < n; end++) {
            sum += arr[end];

            // If sum becomes too large, shrink the window
            while (sum >= k) {
                sum -= arr[start];
                start++;
            }

            // Count valid subarrays ending at end
            count += (end - start + 1);
        }

        return count;
    }

    public static void main(String[] args)
    {
        int[] arr = { 1, 11, 2, 3, 15 };
        int k = 10;

        System.out.println(countsubarray(arr, k));
    }
}

# Function to count subarrays having sum less than k
def countsubarray(arr, k):
    
    n = len(arr)
    start = 0
    sum = 0
    count = 0

    # Move end pointer
    for end in range(n):
        sum += arr[end]

        # If sum becomes too large, shrink the window
        while sum >= k:
            sum -= arr[start]
            start += 1

        # Count valid subarrays ending at end
        count += (end - start + 1)

    return count


if __name__ == "__main__":
    arr = [1, 11, 2, 3, 15]
    k = 10

    print(countsubarray(arr, k))

using System;

class GFG {
    // Function to count subarrays having sum less than k
    static int countsubarray(int[] arr, int k)
    {
        int n = arr.Length;
        int start = 0;
        int sum = 0;
        int count = 0;

        // Move end pointer
        for (int end = 0; end < n; end++) {
            sum += arr[end];

            // If sum becomes too large, shrink the window
            while (sum >= k) {
                sum -= arr[start];
                start++;
            }

            // Count valid subarrays ending at end
            count += (end - start + 1);
        }

        return count;
    }

    static void Main()
    {
        int[] arr = { 1, 11, 2, 3, 15 };
        int k = 10;

        Console.WriteLine(countsubarray(arr, k));
    }
}

// Function to count subarrays having sum less than k
function countsubarray(arr, k)
{
    let n = arr.length;
    let start = 0;
    let sum = 0;
    let count = 0;

    // Move end pointer
    for (let end = 0; end < n; end++) {
        sum += arr[end];

        // If sum becomes too large, shrink the window
        while (sum >= k) {
            sum -= arr[start];
            start++;
        }

        // Count valid subarrays ending at end
        count += (end - start + 1);
    }

    return count;
}

// driver code
let arr = [ 1, 11, 2, 3, 15 ];
let k = 10;

console.log(countsubarray(arr, k));

4