Longest subarray with sum at most k

Given an array of integers A[], find the length of the longest subarray with the sum at most k where k is an integer. For example:

Input:
A[] = [10, 5, 2, 7, 1, 9], 
k = 15
Output:
4
Explanation
longest subarray with sum at most K is [ 5, 2, 7, 1 ].

Input:
A[] = {-5, 8, -14, 2, 4, 12},
k = 5
Output:
5

Longest subarray with a sum k

First of all, if you are not aware of the fundamentals of a sliding window, I would strongly recommend reading: Sliding window concept

The question is how do we know that this is a sliding window problem? Two hints are present in the problem itself, first, we are looking for a subarray i.e. a window, and second, that window has a certain property i.e with a sum of elements at most k.

We will follow the standard pattern for the sliding window; define two pointers, left(l)and right(r). l shrinks the window whenever a property of the window is violated and r expands the window. Every time we expand the window, we add the number to the current sum. If the sum becomes greater than k, we note down the length of this window and update the maximum length if this greater than the previous length. Then we start shrinking the window and subtract the numbers from the sum until the sum is less or equal to k again.

Let’s take an example and see how it works.
Longest subarray with sum at most k

Show me the implementation

package AlgorithmsAndMe;

public class SubarrayWithSumK {
    public int lengthOfSubarray(int[] a, int k){
        int l = 0;
        int r = 0;

        int len = a.length;
        int max = 0;
        int currentSum = 0;

        while(r < len){
            currentSum += a[r];

            while(l < r && currentSum > k){
                max = Math.max(max, r -l);
                currentSum -= a[l];
                l++;
            }
            r++;
        }

        return max;
    }
}

The time complexity of the above code is linear i.e O(n) with O(1) space complexity.

If you are interested, there is another similar problem on Leetcode called Subarray Product Less Than K, you can try there.

Error loading source code.

Show me the answer

class Solution {
    public int numSubarrayProductLessThanK(int[] nums, int k) {
       
        int l = 0;
        int r = 0;

        if(k == 0) return 0;
        int len = nums.length;
        int count = 0;
        int currentProd = 1;

        while(r < len){
            currentProd *= nums[r];

            while(l <= r && currentProd >= k){
                currentProd /= nums[l];
                l++;
            }
            count += r - l + 1;
            r++;
        }
        
        return count;
    }
}

Interview coming up? Check out our full coding interview prep course. There’s a get-the-job-or-your-money-back guarantee, so it only costs money if it actually works.

As always, shoot me an email if there’s anything I can help with.

Longest Substring Without Repeating Characters

Given a string, find the longest substring without repeating characters in it. For example,

Input:
S = "abcaabaca" 
Output:
3
Explanation:
The longest substring without repeating characters will be "abc"

Input: 
"bbbbb"
Output:
1
Explanation:
The answer is "b", with a length of 1.

A brute force solution will be to scan all substrings of the given string and check which one has the longest length and no repeating characters. For a string with size n, there will be n * (n-1) substrings, and to check it each for unique characters, it will take n comparison in the worst case. So, the worst-case complexity of this algorithm is O(n3) with additional space of O(n). The code is simple enough.

package com.company;

import java.util.HashMap;

/**
 * Created by sangar on 1.1.18.
 */
public class NonRepeatingCharacters {

     boolean allUniqueCharacters(String s, int start, int end) {

        HashMap<Character, Boolean> characters = new HashMap<>();

        for (char c : s.substring(start, end).toCharArray()) {
            if(characters.containsKey(c)) return false;
            characters.put(c, Boolean.TRUE);
        }
        return true;
    }

    int longestSubstringWithoutRepeatingCharacters(String s) {
        int len = s.length();
        int maxLength = 0;
          
        for (int i =0; i < len; i++){
            for (int j=i+1; j<len; j++){
                int length = j-i;
                if (allUniqueCharacters(s, i, j)){
                    maxLength = Integer.max(maxLength, length);
                }
            }
        }
        return maxLength;
    }

    public static void main(String[] args) {
        String s = "abcdabcbb";
        System.out.println(longestSubstringWithoutRepeatingCharacters(s));
    }
}

Sliding window approach

A sliding window is an abstract concept commonly used in array/string problems. A window is a range of elements in array/string which defined by start and end indices. A sliding window is a window which “slides” its two boundaries in a certain direction.
Read fundamentals and template for a sliding window to understand more about it and how it is applied to problems.

In the brute force approach, we repeatedly checked each substring for unique characters. Do we need to check each substring? If a substring s[i,j-1] contains non repeating characters, while adding jth character, check if that character is already present in substring s[i,j-1]. Since we scan substring to ascertain the uniqueness of new characters, the complexity of this algorithm is O(n2).

How about optimizing the scanning part? What if a hash is used to store characters which are already seen in substring s[i,j-1]. In that case, checking the uniqueness of a new character is done in O(1) and overall algorithm complexity becomes linear.

 public  static int longestSubstringWithoutRepeatingCharacters(String s) {
        int len = s.length();
        HashMap<Character, Boolean> characters = new HashMap<>();

        int maxLength = 0;
        int start = 0;
        int  end = 0;
        while (start < len && end < len) {
            //Check only the last character.
            if(!characters.containsKey(s.charAt(end))){
                characters.put(s.charAt(end), Boolean.TRUE);
                end++;
            }
            else {
                int currentLength = end-start;
                maxLength = Integer.max(maxLength, currentLength);
                //Move start of window one position ahead.
                characters.remove(s.charAt(start));
                start++;
            }
        }
        return maxLength;
    }

If a character already present in substring s[i,j-1], that means, it cannot be added to the longest substring. Find the length of substring (j-i) and compare it with the current maximum length. if it is greater, the max length of the longest substring without repeating characters is (j-i).
At last move the window to the position of duplicate.

Below is an example execution of the above code.
longest substring without repeating characters

Longest substring without repeating characters : 3

There is a small optimization that helps us to skip more characters when repeating character is found instead of skipping one at a time. Store the index of each character seen in substring [i,j-1].  While processing jth character, if it is already in the hash, we know the index k where that character is in the string. There is no way that any substring can contain unique characters till k and j are in it. So, we skip all indices from i to k and start from k+1 instead of i+1 as in the above method.

Show me the optimized code

  public static int longestSubstringWithoutRepeatingCharacters3(String s) {
        int len = s.length();
        HashMap<Character, Integer> characters = new HashMap<>();

        int maxLength = 0;

        for (int start=0, end = 0; end <len; end++) {
            if (characters.containsKey(s.charAt(end))) {
                //find the index of duplicate character.
                int currentIndex = characters.get(s.charAt(end));
                start = Integer.max(currentIndex, start) + 1;
            }
            int currentLength = end - start;
            maxLength = Integer.max(maxLength, currentLength);
            //Update new location of duplicate character
            characters.put(s.charAt(end), end );
        }
        return maxLength;
    }

Complexity of find longest substring without repeating characters is hence O(n) with additional space complexity of O(n).
Please share if something is wrong or missing. We would love to hear from you.

Find k number in sliding window problem

Sliding window problem

Given a large integer array of size x, window size of n and a random number k, find smallest k numbers in every window of n elements in array. This is commonly know as sliding window problem. For example: for an array [2,3,1,5,6,4,2,5,4,3,8] k = 2 and n = 6, output should be [1,2],[1,2],[1,3][1,4][1,3][1,3]. How? see below figure.

This problem regularly features in Amazon interviews.

Find k numbers in sliding window : thoughts

If we spit down the problem, it reduces to find k smallest elements in an array, which can easily be solve in multiple ways. All we have to take care of is moving the window and storing results for each window.

Quick sort method
First way is to use quick sort, we randomly pick a pivot and put it in right place. When pivot is at right place, all elements on the right side of pivot are greater than pivot and all elements on the left side are less than pivot. If pivot is a kth position in array, all elements on left side of pivot automatically become K smallest elements of given array. In worst case this method take O(n log n) for each window.

Using heaps
What are we interested in is k elements, what if from current window, we take out first k numbers and consider them as k smallest elements? This set of k numbers may change based value of following numbers in the window. Which way? If new number is smaller than any of the number chosen randomly, new number has to be added into the k smallest element set. However, we have only k spaces there, so someone has to move out.

If new number is less than any number in set, it must be less than maximum number in set

Given above fact, we can always swap new number with maximum of set. Now problem is how to find max in a set? This set will modified repeatedly, so we cannot just sort it once and find the max. For use cases when data is changing and we have to find max of that set, heaps are the best data structures to use. In this case we will use max heap. Max heap is kind of heap where children of root node are smaller than root node. Max heap will give us O(1) complexity to find max and O(log n) complexity to heapify on removal old max and insertion of new number.

Algorithm

  1. Create a max heap with first k elements of window.
  2. Scan through remaining elements in window
    1. If root of max heap is less than new number, remove the root and add new element to heap
    2. All elements in heap at the end of processing are k smallest numbers in window.

    Sliding window algorithm to find k smallest elements : Implementation

    #include<stdio.h>
    #include<stdlib.h>
    #include <math.h>
    
    typedef struct node {
    	struct node * left;
    	struct node * right;
    	int data;
    } heapNode;
    
    int leftChild(int i){
    	return 2*i + 1;
    }
    
    int rightChild(int i){
    	return 2*i + 2;
    }
    
    void swapPtr(heapNode *a[], int i, int largest){
    	heapNode *temp = a[i];
    	a[i] = a[largest];
    	a[largest] = temp;
    }
    /* This function heapifies heap after removal of root  
    or at time of building heap from an array */
    void max_heapify_ptr(heapNode *a[], int i, int len){
            int largest = i;
            int left, right;
    
            left = leftChild(i);
            right = rightChild(i);
           
            if(left <= len && a[i]->data <a[left]->data){
                    largest = left;
            }
            if(right <= len && a[largest]->data < a[right]->data){
                    largest = right;
            }
            if(largest != i){
                    swapPtr(a, i, largest);
                    max_heapify_ptr(a, largest, len);
            }
    }
    
    /* Building heap from given elements */
    void build_max_heap_ptr(heapNode *a[], int len){
            int i = len/2 +1;
            for(; i>=0; i--){
                    max_heapify_ptr(a,i, len);
            }
    }
    
    /* This function allocates node of heap */
    heapNode * create_node(int data){
            heapNode *node = (heapNode *)(malloc)(sizeof(heapNode));
            if(node){
                    node->data = data;
            }
            return node;
    
    }
    
    /* This function is real implementation of 
    the sliding window algorithm */
    void slide_window(int buffer[], int N, int K, int buffer_len){
    
        int i =0, j =0,s;
        heapNode *max_heap[K+1];
        int num = K;
    
        for(j=0 ; j + N < buffer_len; j++){
          /* Window starts at index 0 and is of size N */
           printf("\nCurrent window :");
           for(s =j; s<j+N; s++){
               printf("%d ", buffer[s]);
           }
           printf("\n");
           /* Put K element from N element window */
           for(i=0;i<K; i++){
           /* Since we wold be doing for every window, 
              avoiding reallocation of node */
               if(max_heap[i]){
                    max_heap[i]->data = buffer[i+j];
                }
                else{
                    max_heap[i] = create_node(buffer[i+j]);
                }
            }
            /* Build min heap with those entered elements */
             build_max_heap_ptr(max_heap,K-1);
    
            /*Now for all remaining N-K-1 elements in window, 
             check if they fit in max heap */ 
             for(i=K+j; i< N+j; i++){
                 heapNode * root = max_heap[0];
                 if(buffer[i] < root->data){
                       root->data = buffer[i];
                       max_heapify_ptr(max_heap, 0, K-1);
                  }
              }
              
              /*Print the current max heap, it will contain K smallest 
                element in current window */
               printf("K minimum elements in this window :");
               for(int x=0; x< K; x++){
               	printf("%d ", max_heap[x]->data);
               }
               
               
            }
    }
    /* Driver Program to execute above code */
    int main(){
       int buffer[10] = {1,4,5,6,3,2,4,8,9,6};
    
       int K= 4;
       int N =5;
       
       int size = sizeof(buffer)/ sizeof(buffer[0]);
       
       slide_window(buffer,N, K,size);
       return 0;
    }
    

    Following figures explain how window slides and how heap is updated.
    1. Window starts at index 0 and ends at N. We take K minimum elements among N elements and store in max heap. Array is given in below picture with window size of 9 and k = 4.
    First step is to create a max heap with first 4 elements of window.

    sliding window problem

    Next we are looking at 4, which is less than max in max heap. So we remove the max from heap and add the new element(4) to heap.

    k smallest element in sliding window

    Next is 2, which is less than max in max heap. So we remove the max from heap and add the new element(2) to heap.

    Next is 3, which is less than max in max heap. So we remove the max from heap and add the new element(3) to heap.

    Next we have 10 and 11 which are greater than root of max heap, so nothing happens.

    We come to end of window. Therefore, 4 smallest element in window are [ 1,2,3,4 ]

    Next window moves one step ahead, that’s where you discard the max heap and create the new empty one and repeat the process.

    We can actually avoid discarding the entire heap when window moves, however complexity of overall algorithm will remain the same. This problem is asked in a different way, which is to find maximum in sliding window.

    #include <iostream>
    #include<deque>
    using namespace std;
    
    void slidingWindow(int buffer[], int n, int w, int output[])
    {
       deque<int> Q;
       int i;
       /*Initilize deque Q for first window, put all W elements, however also
       removing elements which cannot be maximum in this window */
       for (i = 0; i < w; i++)
       {
       	   //This is where we are removing all less than elements
           while (!Q.empty() && buffer[i] >= buffer[Q.back()])
               Q.pop_back();
           // Pushing the index
           Q.push_back(i);
       }
      
       for (i = w; i < n; i++)
       {
           output[i-w] = buffer[Q.front()];
    
           //update Q for new window
           while (!Q.empty() && buffer[i] >= buffer[Q.back()])
               Q.pop_back();
    
           //Pop older element outside window from Q    
           while (!Q.empty() && Q.front() <= i-w)
               Q.pop_front();
          
           //Insert current element in Q
           Q.push_back(i);
       }
       output[n-w] = buffer[Q.front()];
    }
    
    int main(){
    	int a[]={3,5,4,2,-1,4,0,-3};
    	int n = sizeof(a)/sizeof(a[0]);
    	int output[n];
    
    	slidingWindow(a,n,4,output);
    	return 0;
    }
    

    Worst case complexity of sliding window algorithm would be O(n2k). K is included as it takes O(k) complexity to build heap of k elements.

    Please share if there is something wrong or missing.