Java Programming

 

Problem Statement 

Given an array of positive numbers and a positive number ‘k’, find the maximum sum of any contiguous subarray of size ‘k’.

Example 1:

Input: [2, 1, 5, 1, 3, 2], k=3 

Output: 9

Explanation: Subarray with maximum sum is [5, 1, 3].

Example 2:

Input: [2, 3, 4, 1, 5], k=2 

Output: 7

Explanation: Subarray with maximum sum is [3, 4].

 

Solution #

A basic brute force solution will be to calculate the sum of all ‘k’ sized subarrays of the given array, to find the subarray with the highest sum. We can start from every index of the given array and add the next ‘k’ elements to find the sum of the subarray.

Following is the visual representation of this algorithm for Example-1:

Code

Here is what our algorithm will look like:

Code (Java)

 

class MaxSumSubArrayOfSizeK {

  public static int findMaxSumSubArray(int k, int[] arr) {

    int maxSum = 0, windowSum;

    for (int i = 0; i <= arr.length - k; i++) {

      windowSum = 0;

      for (int j = i; j < i + k; j++) {

        windowSum += arr[j];

      }

      maxSum = Math.max(maxSum, windowSum);

    }

 

    return maxSum;

  }

  

  public static void main(String[] args) {

    System.out.println("Maximum sum of a subarray of size K: "

        + MaxSumSubArrayOfSizeK.findMaxSumSubArray(3, new int[] { 2, 1, 5, 1, 3, 2 }));

    System.out.println("Maximum sum of a subarray of size K: "

        + MaxSumSubArrayOfSizeK.findMaxSumSubArray(2, new int[] { 2, 3, 4, 1, 5 }));

  }

}

 

The time complexity of the above algorithm will be $$O(N*K)O(N∗K), where ‘N’ is the total number of elements in the given array. Is it possible to find a better algorithm than this?

A better approach #

If you observe closely, you will realize that to calculate the sum of a contiguous subarray we can utilize the sum of the previous subarray. For this, consider each subarray as a Sliding Window of size ‘k’. To calculate the sum of the next subarray, we need to slide the window ahead by one element. So to slide the window forward and calculate the sum of the new position of the sliding window, we need to do two things:

1.      Subtract the element going out of the sliding window i.e., subtract the first element of the window.

2.     Add the new element getting included in the sliding window i.e., the element coming right after the end of the window.

This approach will save us from re-calculating the sum of the overlapping part of the sliding window. Here is what our algorithm will look like:

 

class MaxSumSubArrayOfSizeK {

  public static int findMaxSumSubArray(int k, int[] arr) {

    int windowSum = 0, maxSum = 0;

    int windowStart = 0;

    for (int windowEnd = 0; windowEnd < arr.length; windowEnd++) {

      windowSum += arr[windowEnd]; // add the next element

      // slide the window, we don't need to slide if we've not hit the required window size of 'k'

      if (windowEnd >= k - 1) {

        maxSum = Math.max(maxSum, windowSum);

        windowSum -= arr[windowStart]; // subtract the element going out

        windowStart++; // slide the window ahead

      }

    }

 

    return maxSum;

  }

 

  public static void main(String[] args) {

    System.out.println("Maximum sum of a subarray of size K: "

        + MaxSumSubArrayOfSizeK.findMaxSumSubArray(3, new int[] { 2, 1, 5, 1, 3, 2 }));

    System.out.println("Maximum sum of a subarray of size K: "

        + MaxSumSubArrayOfSizeK.findMaxSumSubArray(2, new int[] { 2, 3, 4, 1, 5 }));

  }

}

Time Complexity 

The time complexity of the above algorithm will be $$O(N)

Space Complexity 

The algorithm runs in constant space $$O(1)

⎻⎻⎻⎻⎻⎻⎻⎻⎻⎻⎻⎻⎻⎻⎻⎻⎻⎻⎻⎻⎻⎻⎻⎻⎻⎻⎻⎻⎻⎻⎻⎻⎻⎻⎻⎻⎻⎻⎻⎻⎻⎻⎻⎻⎻⎻⎻⎻⎻⎻⎻⎻⎻⎻⎻⎻⎻⎻⎻⎻⎻⎻⎻⎻⎻⎻⎻⎻⎻⎻⎻⎻

Problem 2 (Given a string, find the length of the longest substring in it with no more than K distinct characters.)

import java.util.*;

 

class LongestSubstringKDistinct {

  public static int findLength(String str, int k) {

    if (str == null || str.length() == 0 || str.length() < k)

      throw new IllegalArgumentException();

 

    int windowStart = 0, maxLength = 0;

    Map<Character, Integer> charFrequencyMap = new HashMap<>();

    // in the following loop we'll try to extend the range [windowStart, windowEnd]

    for (int windowEnd = 0; windowEnd < str.length(); windowEnd++) {

      char rightChar = str.charAt(windowEnd);

      charFrequencyMap.put(rightChar, charFrequencyMap.getOrDefault(rightChar, 0) + 1);

      // shrink the sliding window, until we are left with 'k' distinct characters in the frequency map

      while (charFrequencyMap.size() > k) {

        char leftChar = str.charAt(windowStart);

        charFrequencyMap.put(leftChar, charFrequencyMap.get(leftChar) - 1);

        if (charFrequencyMap.get(leftChar) == 0) {

          charFrequencyMap.remove(leftChar);

        }

        windowStart++; // shrink the window

      }

      maxLength = Math.max(maxLength, windowEnd - windowStart + 1); // remember the maximum length so far

    }

 

    return maxLength;

  }

 

  public static void main(String[] args) {

    System.out.println("Length of the longest substring: " + LongestSubstringKDistinct.findLength("araaci", 2));

    System.out.println("Length of the longest substring: " + LongestSubstringKDistinct.findLength("araaci", 1));

    System.out.println("Length of the longest substring: " + LongestSubstringKDistinct.findLength("cbbebi", 3));

  }

}

Problem 3 : Given an array of characters where each character represents a fruit tree, you are given two baskets and your goal is to put maximum number of fruits in each basket. The only restriction is that each basket can have only one type of fruit.

Here is what our algorithm will look like,

 

import java.util.*;

 

class MaxFruitCountOf2Types {

  public static int findLength(char[] arr) {

    int windowStart = 0, maxLength = 0;

    Map<Character, Integer> fruitFrequencyMap = new HashMap<>();

    // try to extend the range [windowStart, windowEnd]

    for (int windowEnd = 0; windowEnd < arr.length; windowEnd++) {

      fruitFrequencyMap.put(arr[windowEnd], fruitFrequencyMap.getOrDefault(arr[windowEnd], 0) + 1);

      // shrink the sliding window, until we are left with '2' fruits in the frequency map

      while (fruitFrequencyMap.size() > 2) {

        fruitFrequencyMap.put(arr[windowStart], fruitFrequencyMap.get(arr[windowStart]) - 1);

        if (fruitFrequencyMap.get(arr[windowStart]) == 0) {

          fruitFrequencyMap.remove(arr[windowStart]);

        }

        windowStart++; // shrink the window

      }

      maxLength = Math.max(maxLength, windowEnd - windowStart + 1);

    }

 

    return maxLength;

  }

 

  public static void main(String[] args) {

    System.out.println("Maximum number of fruits: " + 

                          MaxFruitCountOf2Types.findLength(new char[] { 'A', 'B', 'C', 'A', 'C' }));

    System.out.println("Maximum number of fruits: " + 

                          MaxFruitCountOf2Types.findLength(new char[] { 'A', 'B', 'C', 'B', 'B', 'C' }));

  }

}

 

Problem 4 :

Cyclic Sort (easy)

Problem Statement

We are given an array containing ‘n’ objects. Each object, when created, was assigned a unique number from 1 to ‘n’ based on their creation sequence. This means that the object with sequence number ‘3’ was created just before the object with sequence number ‘4’. (Concept)

Java Code :

class CyclicSort {

 

  public static void sort(int[] nums) {

    int i = 0;

    while (i < nums.length) {

      int j = nums[i] - 1;

      if (nums[i] != nums[j])

        swap(nums, i, j);

      else

        i++;

    }

  }

 

  private static void swap(int[] arr, int i, int j) {

    int temp = arr[i];

    arr[i] = arr[j];

    arr[j] = temp;

  }

 

  public static void main(String[] args) {

    int[] arr = new int[] { 3, 1, 5, 4, 2 };

    CyclicSort.sort(arr);

    for (int num : arr)

      System.out.print(num + " ");

    System.out.println();

 

    arr = new int[] { 2, 6, 4, 3, 1, 5 };

    CyclicSort.sort(arr);

    for (int num : arr)

      System.out.print(num + " ");

    System.out.println();

 

    arr = new int[] { 1, 5, 6, 4, 3, 2 };

    CyclicSort.sort(arr);

    for (int num : arr)

      System.out.print(num + " ");

    System.out.println();

  }

}