Category Archives: Sliding Window

Subarray with Given Sum

By | | , , ,
Leave a comment

Find subarray with given sum.

Given an array of unsorted integers (Positive integers), We have to write a code to find a subarray whose sum is equal to a given sum.

We have to return subarray indexes (start and end index).

For Example –

  Example 1 :

Input : arr = {10, 2, 4, 7, 5}, sum = 13

Output: {1, 3}

The numbers present from the 1st to 3rd indexes are 2, 4, 7. When we add (2 + 4 + 7) it is 13.

Example 2 :

Input : arr = {1, 4, 20, 3, 10, 5}, sum = 33

  Output: {2, 4}

Example 3 :

  Input : arr = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}, sum = 15

   Output: {0, 4}

→

Count Distinct Elements in Every Window of Size K

By | | , ,
Leave a comment

Count Distinct Elements in Every Window of Size K.

Given an array of n integers and an integer k (k is always smaller or equal to n).  Return the count of distinct elements in all windows (or in all sub-arrays) of size k.

For example –

   Example 1:

  Input: {1, 5, 9, 3, 3, 7, 3},   k = 3

  Output: {3, 3, 2, 2, 2}

1st window {1, 5, 9}, Distinct elements are 3.

2nd window {5, 9, 3}, Distinct elements are 3.

3rd window {9, 3, 3}, Distinct elements are 2.

4th window {3, 3, 7}, Distinct elements are 2.

5th window {3, 7, 3}, Distinct elements are 2.

   Example 2:

  Input: {1, 4, 7, 7},   k = 2

  Output: {2, 2, 1}

1st window {1, 4}, Distinct elements are 2.

2nd window {4, 7}, Distinct elements are 2.

3rd window {7, 7}, Distinct elements are 1.

→

Minimum Size Subarray Sum

By | | , , , ,
Leave a comment

Minimum Size Subarray Sum (Smallest subarray whose sum is greater than or equal to target).

Given an array of positive integers and a positive number k. Find the smallest contiguous subarray whose sum is either greater than or equal to k. If no subarray is found then return 0.

For example –

Example 1 –

  Input :  {7, 2, 1, 1, 6, 5},  k = 11

Output:  2 ( subarray {6, 5} has the minimum length )

Example 2 –

  Input : {1, 4, 3},   k = 12

Output: 0 (No subarray is possible)

→