Basically, we need to determine the first and last occurrence of a duplicate key element in the Array. Consider this array for example:

Here, we can see an array of size 10 with duplicate elements 5 and 7. If we want to know the first and last occurrence of element 5, it will be at index 3 and 4 respectively. Similarly, for element 7, the first and last occurrence is at position/index 5 and 7 respectively.

Input: Array = {2,3,4,5,5,7,7,7,9,11}, target = 7
Output: 5,7                          // Comma separated Index of First and Last Occurrence.

Input: Array = {5,6,6,6,7,8,8,10}, target = 8
Output: 5,6

Now let us look at our approaches to solve this problem.

Approach 1 (Using Linear Search)

In this method, we will follow these steps:

• At first, we will traverse the array from the beginning or start index of the array. As soon as we get the target element, we store its index. This will indicate the first occurrence position of the target element. Then, we break out of the loop and stop traversing.
• Now, to get the last index, we will start traversing from the end index of the array and as soon as we get the target element, we store its index. This will indicate the last occurrence of the element. Then, we simply print those indices.

Let us look at the code for this method:

import java.util.*;

public class Example
{

  static void findFirstAndLastPosition(int arr[],int n,int target)
  {
     // We initialize first and last as -1 if the target is not present in the array.
      int first = -1;
      int last = -1;

      for(int i=0;i<n;i++)
      {
          if(arr[i] == target)
          {
              first = i;
              break;
          }
      }

      for(int i=n-1;i>=0;i--)
      {
          if(arr[i] == target)
          {
              last = i;
              break;
          }
      }

      System.out.println("The First occurrence of "+target+" at index : "+first+" and the Last occurrence is at index : "+last);
  }

  public static void main(String args[])
  {
   int arr[] = new int[]{2,3,4,5,5,7,7,7,9,11};
   int n = arr.length;

   int target = 7;
   findFirstAndLastPosition(arr,n,target);

  }

}

Output:

The First occurrence of 7 at index : 5 and the Last occurrence is at index : 7

Time Complexity: Here we perform a Linear Search to get the indexes if the the first occurrence is at second last element then we have to traverse the whole array. So, the overall runtime is O(n).

Approach 2 (Using Modified Binary Search-Optimal)

The idea or purpose of this approach is to minimize the runtime of the above method by using and modifying the Binary Search Algorithm. The breakdown of this approach is shown below:

• Basically, We implement two functions:
  1. findStartingIndex(Array,target) -> To get the Starting Index or First Occurrence of Target element.
  2. findEndingIndex(Array,target) -> To get the Ending Index or Last Occurrence of Target element.

• Now, for findStartingIndex() method, we will search the target by performing a modified binary search. We calculate mid = (low + high) / 2 (low =0 and high = Array_Size – 1). As the array is sorted, for each value of mid we need to perform operations based on three conditions.
  1. If(Arr[mid] >= target) -> This means if the element at index mid is greater than target element, then to get closer to target we need to update high = mid - 1 and search in the left half of the array. If the element is equal to target then also we need to update high, this will ensure we get as close as possible to the First Occurrence of the target.
  2. If the first condition does not hold true, it means the element is smaller than target, so we update low = mid + 1 and expand our search to the right half of the array.
  3. If(Arr[mid] == target) -> If we get the element at index mid equal to target, we store its index as a possible solution and continue our search until low<=high.
• Similarly for findEndingIndex() method, we search the target by making some changes. The algorithm remains the same as the method discussed above only the conditions need to be changed.
  1. If(Arr[mid] <= target) -> If the element at index mid is smaller than target, then to get closer to target we update low = mid + 1, instead of high and continue searching in the right half of array. If the element is equal then also we update low and get close to the Last occurrence of the target.
  2. If the first condition is not true, we update high = mid -1 and search in the left half of array as element at mid is greater than the target.
  3. If(Arr[mid] == target) -> If the element is equal, we store its index and continue these steps until low<=high.

Let us look at the implementation of above approach:

import java.util.*;

public class Example
{
  //finds Starting Index or First occurrence of target.
  static int findStartingIndex(int arr[],int n,int target)
  {
      int low = 0;
      int high = n-1;
      int index = -1;

      while(low <= high)
      {
      // Calculate mid value.      
      int mid = (low+high)/2;

      //Condition 1
      if(arr[mid]>=target)
      {
          high = mid-1;
      }
      // Condition 2 : When arr[mid] < target
      else
      {
          low = mid+1; 
      }
      // Condition 3
      if(arr[mid] == target)
      {
          index = mid;
      }

      }

      return index;
  }

  //finds Last occurrence of target.
  static int findEndingIndex(int arr[],int n,int target)
  {
      int low = 0;
      int high = n-1;
      int index = -1;

      while(low <= high)
      {
      // Calculate mid value.      
      int mid = (low+high)/2;

      //Condition 1
      if(arr[mid]<=target)
      {
          low = mid+1;
      }
      // Condition 2 : When arr[mid] > target
      else
      {
          high = mid-1; 
      }
      // Condition 3
      if(arr[mid] == target)
      {
          index = mid;
      }

      }

      return index;
  }

  static void findFirstAndLastPosition(int arr[],int n,int target)
  {
      int first = findStartingIndex(arr,n,target);
      int last = findEndingIndex(arr,n,target);
      System.out.println("The First occurrence of "+target+" at index : "+first+" and the Last occurrence is at index : "+last);
  }

  public static void main(String args[])
  {
   int arr[] = new int[]{5,6,6,6,7,8,8,10};
   int n = arr.length;

   int target = 8;
   findFirstAndLastPosition(arr,n,target);

  }

}

Output:

The First occurrence of 8 at index : 5 and the Last occurrence is at index : 6

Time complexity: We used Binary Search to get the first and last occurrence of the target element. We know binary search has runtime O(log n). Henceforth, the calls for findStartingIndex() and findEndingIndex() methods take O(log n) time each. So, the overall complexity is O(log n + log n) = O(log n). This is an optimal approach for this problem.

That’s all about Search for a range Leetcode – Find First and Last Position of Element in Sorted Array.

If you want to practice data structure and algorithm programs, you can go through Java coding interview questions.

In this post, we will see how to sort an array of 0s, 1s and 2s.We have already seen a post on sort 0s and 1s in an array.

Problem

Given an array containing zeroes, ones and twos only. Write a function to sort the given array in O(n) time complexity.

Solution

APPROACH – I :
A very basic approach to solve this problem can be keeping the count of number of zeroes, ones and twos in the given array and then manipulate the given array in accordance with the frequency of every number. This approach is a bit inspired by counting sort. No matter what the initial value of that particular index is, we first put all the zeroes we have in the array starting from index zero, then put all the ones and after that put all the twos.

Steps:
1.) Traverse the given array once and keep incrementing the count of the number encountered.
2.) Now Traverse the array again starting from index zero and keep changing the value of the element on current index first exhaust all the zeroes then ones and finally all the twos.

This way we have a sorted array where all the zeroes are in starting followed by all the ones and then in last section we have all the twos in a time complexity of O(n).

• But the major drawback of this approach is, we have to traverse the given array twice once for counting the number of zeroes, ones and twos and second one for manipulating the array to make it sorted, which can be done only in a single pass.

package Arrays;

    public class sort012 {

    public static void main(String[] args) {

        int[]a = {1,0,2,0,0,1,2,2,1};
        sort(a);
        for(int val : a)
        {
            System.out.println(val + " ");
        }

    }
    /*Function to sort the given array*/
    public static void sort(int[]a)
    {
        /* array to keep the count of 0s, 1s, 2s*/
        int[]freq = new int[3];

        /* traverse the given array for filling the
         * frequency array*/
        for(int val : a)
        {
            freq[val]++;
        }
        /*pointer to traverse the given array again*/
        int pointer = 0;
        for(int i=0;i<freq.length;i++)
        {
            /* loop to exhaust the number of 0s, 1s, 2s*/
            while(freq[i]-->0)
            {
                /*at the current pointer plot the current number*/ 
                a[pointer]=i;
                /*increment the pointer*/
                pointer++;
            }
        }
    }

APPROACH – II :
This algorithm is called as Dutch national flag algorithm or Three way partitioning in which elements of similar type are grouped together and their collective groups are also sorted in a the correct order.
Now we have three types of elements to be sorted, therefore, we divide the given array in four sections out of which 3 sections are designated to zeroes, Ones and twos respectively and one section is unknown or the section which is left to be explored. Now for traversing in these sections we need 3 pointers as well which will virtually divide the given array in four segments.
Let us name these pointers as low, mid and high.

Now we can tell the starting and ending points of these segments.

• Segment-1 : zeroes
  This will be a known section containing only zeroes with a range of [0, low-1].
• Segment-2: Ones
  This will also be a know section containing only ones with a range of [low, mid-1].
• Segment-3 : Unexplored
  This will be an unknown section as the elements in this sections are yet to be explored and hence it can contain all types of element that is, zeroes, ones and twos. Range of this segment will be [mid, high]
• Segment-4 : Twos
  This will be the last and known area containing only twos having the range of [high+1, N] where N is the length of the given array or basically the last valid index of the given array.

Steps used in this Algorithm to sort the given array in a single pass :

(i) Initialize the low, mid and high pointers to, low = 0, mid = 0, high = N
(ii) Now, run a loop and do the following until the mid pointer finally meets high pointer.As the mid pointer moves forward we keep putting the element at mid pointer to its right position by swapping that element with the element at pointers of respective sections.
(iii) CASE – I : If the element at mid, that is, A[mid] == 0, this means the correct position of this element is in the range [0, low-1], therefore, we swap A[mid] with A[low] and increment low making sure that element with index lesser than low is a Zero.
(iv) CASE – II : If the element at mid, that is, A[mid] == 2, this means the correct position of this element is in the range [hi+1, N], therefore, we swap A[mid] with A[hi] and decrement high making sure that element with index greater than high is a two.
(v) CASE – III : If the element at mid, that is, A[mid]=1, this means that the element is already in its correct segment because [low, mid-1] is the range where it needs to be. Therefore, we do nothing and simply increment the mid pointer.

So, there are total three cases, let us take a moment and emphasise on the fact that mid pointer gets only incremented only when the element A[mid] == 1.
Let us discuss every case individually,

For case – I : In this case we increment mid as well along with increment low pointer, as we are sure that element at low pointer before swapping can surely only be one as had it been a two, it would have already got swapped with high pointer when mid pointer explored it as the only reason that mid pointer left it because it was a one.

For case – II : Now, In this case we swap the element at mid and high, but unlike case – I, in this case we are not sure about the element which will come at mid index after swapping as the element at high index before swapping can be any of zero, one or two, therefore, we need to explore this swapped element and hence we do not increment mid pointer in this case.

For case – III : There is no confusion regarding incrementing mid in this case as already discussed, as we know the element at mid is one therefore we definitely need to increment mid here.

Time complexity of this algorithm is also O(n) but it sorts the array in just a single pass and without any extra space unlike previous approach.

package Arrays;

    public class sort012 {

    public static void main(String[] args) {

        int[]a = {1,2,2,0,0,1,2,2,1};
        sort(a);
        for(int val : a)
        {
            System.out.print(val + " ");
        }

    }

    public static void sort(int[]a)
    {
        /* Three pointers to divide the array in designated segments
         * as discussed in the post*/
        int low=0,mid=0,high=a.length-1;
        while(mid<=high)
        {
            /* Case - 1, when element at mid pointer is zero,
             * swap with element at low*/
            if(a[mid]==0)
            {
                a[low]=swap(a[mid], a[mid]=a[low]);
                /* Increment low as well as mid, as we know
                 * the swapped element at mid is a one*/
                low++;
                mid++;
            }
            /* Case - 1, when element at mid pointer is two,
             * swap with element at high*/
            else if(a[mid]==2)
            {
                /* decrement only high and keep mid unchanged, as
                 * we do not know anything about the swapped element
                 * at mid*/
                a[high]=swap(a[mid],a[mid]=a[high]);
                high--;
            }
            else {
                /*Case - 3, when element at mid pointer is one*/
                /*do nothing, and increment mid pointer*/
                mid++;
            }

        }
    }

    /* utility swap function*/
    public static int swap(int i, int j)
    {
        return i;
    }
}

That’s about sort an array of 0s, 1s and 2s.

If you want to practice data structure and algorithm programs, you can go through Java coding interview questions.





Problem

Given an array with positive integers as elements indicating the maximum length of a jump which can be made from any position in the array. Check if it is possible to have a jumps combination so that you can eventually reach the end of given array. Print "true" if it is possible, otherwise, print "false".

Solution

APPROACH – I (RECURSIVE)

This a very basic brute force approach in which we make all the possible jumps from any current position.
We start with the current position at index zero in the array, and make a recursive call by changing the current position by adding all the possible jump lengths one by one. We also need to make sure that we stay in bounds of the given array, that is why we only make the jump if the current position after adding this jump length stays in bound.

Positive Base case : If the current position is equal to array.length, this means that we have successfully reached the end of the given array, that is, a jumps combination exists with which we can reach end of given array, hence we return true from here.

Negative base case : if maximum length of any jump possible from any current position is equal to zero, this means that there is no way possible with which we can reach the end of the given array as we cannot move even a single position from our current position.

Time complexity Discussion :

As from every point we are making all the possible jumps and in worst case from any position, we can make ‘n’ jumps and there are n possible spots from where we can make these jumps, therefore, worst time complexity of this algorithm for solving this problem is O(n^n), where ‘n’ is the length of the given array.

package Arrays;

import java.util.Scanner;

public class reachEnd {

    public static void main(String[] args) {

        Scanner scn = new Scanner(System.in);
        /*input size of the array*/
        int n = scn.nextInt();
        int[]arr = new int[n];

        /*input elements in the array*/
        for(int i=0;i<arr.length; i++)
        {
            arr[i] = scn.nextInt();
        }

        System.out.println(solve(0, arr));

    }

    public static boolean solve(int cp, int[] arr) {
        /* base case : if the current position of the pointer
         * is at last element of the array which indicates
         * that we have reached the end of the array, then
         * we can return true from here*/
        if (cp == arr.length-1) {
            return true;
        }
        /* if maximum jump which we can make from current
         * position is zero, then there is no way we can
         * reach end of array using the current combination
         * of jumps, hence return false from here */
        if (arr[cp] == 0) {
            return false;
        }
        boolean rv = false;

        /* start from current position, and make all the jumps of
         * possible length, and make a recursive call which
         * eventually changes our current position */
        for (int jump = 1; jump <= arr[cp]; jump++) {
            if(cp + jump < arr.length){
                /* here we use logical 'or' operator because any true
                 * result is sufficient enough to  prove that a jumps 
                 * combination exists with which we can reach end of
                 * given array*/
                rv = rv || solve(cp + jump, arr);
            }
        }
        return rv;
    }

}

APPROACH – II (Iterative) :

In the previous approach we can clearly see so many duplications of recursive call which find the result of same position again and again, therefore, we can use Dynamic Programming to solve the given problem and also reduce the running time complexity of the algorithm.

In this Dynamic Programming approach, we calculate result for every index that is, if it is possible to reach to that ‘i’th index from 0th index with a combination of possible jumps.

Therefore, we make a boolean DP array for storing the result for every index which is false initially except the first index as this is where we start the journey from.

• Some Points which are needed to be considered are :
  (i) We can make further jumps from any position only if that position itself is reachable from Zeroth index.
  (ii) We can not move any further from an index if the maximum allowed length of any jump is Zero.
  Therefore, we can only move from any position only if that position itself is reachable and length of jump allowed from that position is not zero.

Our main motive is to find if there exists a path or jump combination from Zeroth index to Last index.

• To prove this, we can agree on the fact that, If there exist a path or jump combination from Zeroth index to any Intermediate Index, and also there exist a path or jump combination from Intermediate index to Last Index, Then the the last index will surely be reachable from Zeroth index.

Time complexity Discussion :
As in this approach also we are making jumps of all possible lengths which can potentially be ‘n’ in worst case, and we are doing this in loop for every index of the array, then, the worst time complexity of this algorithm for solving this problem is O(n^2), where ‘n’ is length of the given array.

package Arrays;

import java.util.Scanner;

public class reachEnd {

    public static void main(String[] args) {

        Scanner scn = new Scanner(System.in);
        /* input size of the array */
        int n = scn.nextInt();
        int[] arr = new int[n];

        /* input elements in the array */
        for (int i = 0; i < arr.length; i++) {
            arr[i] = scn.nextInt();
        }

        System.out.println( solve(arr));

    }

    public static boolean solve(int[] arr) {
        /* dp array to store the result of every index, that is,
         * if they are reachable or not, true indicates that there
         * exists one or more jump combinations to reach that index,
         * and no jump combination exist in case of a false*/
        boolean[] dp = new boolean[arr.length];

        /* first index is always reachable, as this is the position
         * we start from*/
        dp[0] = true;

        /*finding result for every index*/
        for (int currPos = 0; currPos < arr.length; currPos++) {
            /* if the index we are currently at is not reachable from
             * 0th index, then we obviously can not make further jumps
             * from this position.
             * Also, number of jumps possible from the current position
             * needs to be greater than zero, as in case of zero, we can
             * not move to any other position by making a jump*/
            if (dp [currPos] && arr [currPos] > 0) {
                int maxJumps = arr[currPos];
                /* mark all the reachable positions from current position
                 * true because, if they can be reached from an intermediate
                 * spot, and that intermediate spot can be reached from zero,
                 * then the jumped position will also be reachable from zeroth
                 * index*/
                for (int jump = 1; jump <= maxJumps; jump++) {
                    if(currPos + jump < dp.length)
                    {
                        dp[currPos+jump] =  true;
                    }
                }
            }
        }

        /*return the result of last index of the array if it is reachable
         * from zeroth index or not*/
        return dp [arr.length-1];
    }

}

That’s all about to check if it is possible to reach end of given Array

If you want to practice data structure and algorithm programs, you can go through 100+ data structure and algorithm programs.

In this post, we will see how to check if array elements are consecutive.

Problem

Given an array, we need to check if array contains consecutive elements.
For example:

Solution

Simple solution will be to sort the array and check if elements are consecutive just by iterative over array but time complexity of this solution will be o(n^logn).

Can we do better?
Yes, we can do better

• Find minimum and maximum element in the array.
• Check if max-min+1==n, if elements are consecutive then this condition should meet.
• Create a visited boolean array.
• Iterate over the array and check
  • visited[arr[i]-min] is true, then return false as elements are repeated.
  • mark the element visited.

Program to check if Array Elements are Consecutive

package org.arpit.java2blog;

public class ArrayConsecutiveElementMain{


	/* Method return minimum value*/
	private int getMinimum(int arr[], int n)
	{
		int min = arr[0];
		for (int i = 1; i < n; i++)
			if (arr[i] < min)
				min = arr[i];
		return min;
	}

	/* Method return maximum value*/
	private int getMaximum(int arr[], int n)
	{
		int max = arr[0];
		for (int i = 1; i < n; i++)
			if (arr[i] > max)
				max = arr[i];
		return max;
	}

	/* This method checks if array elements are consecutive */
	public boolean checkArrayContainsConsecutiveElements(int arr[], int n)
	{
		if ( n <  1 )
			return false;

		int min = getMinimum(arr, n);
		int max = getMaximum(arr, n);

		if (max - min  + 1 == n)
		{
			boolean[] visited=new boolean[arr.length];
			for (int i = 0; i < n; i++)
			{
				if ( visited[arr[i] - min] != false )
					return false;

				visited[arr[i] - min] = true;
			}

			return true;
		}
		return false; 
	}
	
	public static void main(String args[])
	{
		ArrayConsecutiveElementMain acem=new ArrayConsecutiveElementMain();
		int arr[]= {47, 43, 45, 44, 46};
		
		if(acem.checkArrayContainsConsecutiveElements(arr, arr.length))
			System.out.println(" Array elements are consecutive ");
		else
			System.out.println(" Array elements are not consecutive ");
		return;
	}
}

When you run above program, you will get below output:

Time complexity of this solution is o(n).

That’s all about how to check if Array Elements are Consecutive.

If you want to practice data structure and algorithm programs, you can go through Java coding interview questions.

In this post, we will see how to find the local minima in the array.

Problem

An element is local minima if it is less than its neighbors.

Solution

Naive approach

You can use for loop and compare neighbor elements, you will get the local minima.
Worst case time complexity will be o(n).

Efficient approach

You can use binary search to find local minima.

Worst case time complexity will be o(log n).
Here is simple algorithm

• Find the mid element
• If mid element is less than both the neighbor then return it.
• If mid element is greater than its left neighbor, then go left
• else go right.

package org.arpit.java2blog;
public class LocalMinima {

    public int findLocalMinima(int [] arr, int start, int end){

        /*find the mid index*/
        int mid = start + (end-start)/2;
        int size = arr.length;

        /*check the local minima 
         *first check if left and right neighbor exists */
        if((mid==0 || arr[mid-1]>arr[mid]) &&
                (mid==size-1 || arr[mid+1]>arr[mid]))
            return arr[mid];
        /* check if left neighbor is less than mid element, if yes go left */
        else if(mid>0 && arr[mid]>arr[mid-1]){
            return findLocalMinima(arr, start, mid);
        }
        else { 
            /*check if right neighbor is greater than mid element, if yes go right */
            return findLocalMinima(arr, mid+1, end);
        }
    }

    public static void main(String[] args) {
        LocalMinima l = new LocalMinima();
        int [] arr = {10, 5, 3, 6, 13, 16, 7};
        System.out.println("Local Minima is: " + l.findLocalMinima(arr,0,arr.length));
    }
}

When you run above program, you will get below output.

That’s all about how to find the local minima in a array

If you want to practice data structure and algorithm programs, you can go through Java coding interview questions.

In this post, we will see about Sliding Window Maximum in java

Problem

Given an Array of integers and an Integer k, Find the maximum element of from all the contiguous subarrays of size K.

For eg :

for every subarray of size k, Print its maximum element.

Solution

Naive Approach :
The basic solution would be just generating all the contiguous subarrays of size k and looping over them for finding out the max in that current subarray.
Considering, for every spot we are basically taking next ‘k’ element and then we loop over those k elements, so the worst time complexity of this algorithm would be O(n*k).

package Arrays;

import java.util.Scanner;

public class slidingWindowMax {

    public static void main(String[] args) {

        Scanner scn = new Scanner(System.in);
        int [] arr = new int[scn.nextInt()];

        for(int i = 0; i < arr.length; i++)
        {
            arr[i] = scn.nextInt();
        }

        int windowSize = scn.nextInt();

        solve(arr, windowSize);

    }

    public static void solve(int[] arr, int k)
    {
        // starting the outer loop from k and running it until, 
                // current pointer is EQUAL to arr.length
        for(int i = k; i <= arr.length; i++)
        {
            int max = Integer.MIN_VALUE;

            // this loop considers subarrays of size k ending at i-1
            for(int j = i-k; j<i; j++)
            {
                max = Math.max(max, arr[j]);
            }

            System.out.println(max);
        }
    }
}

Slightly Efficient Approach:

We can surely reduce the time taken in finding max for every subarray by using Segment tree.
We can Implement a segment tree for the given array, and we can get the max of every subarray with range query [i, i+k-1].

• Total number of nodes in segment tree :
  The worst time complexity for constructing the segment tree would be O(n) because we know,
  (i) Leaf nodes of segment tree contains all the elements of the array.
  (ii) The number of nodes on last level is the number of nodes on all the upper levels.

• Mathematically,

1. Consider length of the array to be n, therefore, leaf nodes of the segment tree will be n.
2. hence, the number of nodes on all the upper levels will be n-1.
3. Total nodes on segment tree for an array of length n will be:
   Tn = leaf nodes + nodes on upper levels
         = n + n-1
         = 2n+1

• Complexity Analysis

The construction of our segment tree involves calculation for every node only once, so worst time complexity of construction of segment tree will be O(2n+1) i.e O(n).
and result for range query of each subarray will be calculate in O(logk).
The query calculation will be done for all the ‘n-k+1’ subarrays of size k.
therefore overall time complexity for this algorithm will be O((n-k+1)*logk) i.e. O(nlogk).

package Arrays;

import java.util.Scanner;

public class slidingWindowMax {

    static int[] sarr;

    public static void main(String[] args) {

        Scanner scn = new Scanner(System.in);
        int[] arr = new int[scn.nextInt()];

        for (int i = 0; i < arr.length; i++) {
            arr[i] = scn.nextInt();
        }

        int windowSize = scn.nextInt();

        int height = (int)Math.ceil((Math.log(arr.length) / Math.log(2)));

        /* size of segment array  i.e. the number of nodes will be = [(2^height+1)-1] */

        sarr = new int[1<<height -1];

        construct(0, 0, arr.length-1, arr);

        solve(arr, windowSize);

    }

    public static void solve(int[] arr, int k) {
        for (int i = 0; i <= arr.length - k; i++) {
            /* finding the result for range query from i to i+k which is basically a subarray.
             * 
             */
            System.out.println(query(0, i, i + k - 1, 0, arr.length - 1));
        }
    }

    public static int construct(int idx, int start, int end, int[] arr) {
        /* leaf nodes contains the array elements */
        if (start == end) {
            sarr[idx] = arr[end];
            return sarr[idx];
        }

        int mid = (start + end) / 2;
        /* dividing the range for every node in segment tree into two halves */
        int left = construct(2 * idx + 1, start, mid, arr);
        int right = construct(2 * idx + 2, mid + 1, end, arr);
        /* result for current index in segment tree will be calculated
         *  in post order, and will be maximum of its two childs.
         */
        sarr[idx] = Math.max(left, right);
        return sarr[idx];
    }

    public static int query(int idx, int queryStart, int QueryEnd, int start, int end) {
        /* if our range is completely outside the query, 
         * we need to return a result such that it causes no effect in our final answer.
         */

        if (start > QueryEnd || end < queryStart) {
            return Integer.MIN_VALUE;
        } 
        /* if the range of the current segment falls completely
         *  inside the query then return its value.
         */
        else if (start >= queryStart && end <= QueryEnd) {
            return sarr[idx];
        } else {

            int mid = (start + end) / 2;
            int left = query(2 * idx + 1, queryStart, QueryEnd, start, mid);
            int right = query(2 * idx + 2, queryStart, QueryEnd, mid + 1, end);

            return Math.max(left, right);
        }
    }
}

Most Efficient Approach :

In this approach we use Deque which helps us finding the sliding window maximum in O(n).

• A Deque is basically a queue which is open on both the ends for both enqueue and Deque, that is, you can add or remove element either from front or rear.

What we actually do to solve the problem is:

we keep the k elements of the subarrays in the reverse sorted order, We need not keep all the k elements though which we will see later in code.

• Generate the Deque for the first k elements, keeping them sorted in reverse order so that the maximum element is at the front.
• If the Deque is empty, add the element straightaway, else check if the incoming element is greater than the last element, if it is, keep popping the elements from last until the last element of the remaining Deque is greater than the incoming element.
• We also need to remove the elements which belong to different subarray. i.e the indices in the Deque must be in the range, [i, i+k].

An element will only be removed on two conditions :
(i) If the upcoming element is greater than the element at rear, if it, it will keep on popping the element until there comes a larger element at rear of remaining dequeue because we need to keep the array sorted in the reverse order.
(ii) If the element belongs to any other subarray then there is no point in keeping it.

package org.arpit.java2blog;

import java.util.LinkedList;
import java.util.Scanner;

public class SlidingWindowMax {

    static int[] sarr;

    public static void main(String[] args) {

        Scanner scn = new Scanner(System.in);
        int[] arr = new int[scn.nextInt()];

        for (int i = 0; i < arr.length; i++) {
            arr[i] = scn.nextInt();
        }

        System.out.print("arr[]: {");
        for (int i = 0; i < arr.length; i++) {
            System.out.print(" "+arr[i]);
        }

        System.out.println(" }");

        int windowSize = scn.nextInt();

        solveEfficient(arr, windowSize);

    }

    public static void solveEfficient(int[] arr, int k) {
        LinkedList<Integer> deque = new LinkedList<>();

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

            /* keep removing the elements from deque 
             * which are smaller than the current element, 
             * because we need to keep our deque sorted in dec order 
             */
            while (!deque.isEmpty() && arr[deque.getLast()] <= arr[i]) {
                deque.removeLast();
            }

            /* removing the i-k element, because that element does not belong 
             * to the subarray we are currently working on.
             */
            while (!deque.isEmpty() && deque.getFirst() <= i - k) {
                deque.removeFirst();
            }

            deque.addLast(i);

            if(i >= k-1)
            {   
            /* only print when we have processed atleast k elements 
             * to make the very first subarray
             */
                System.out.print(" "+arr[deque.getFirst()]);
            }

        }
    }
}

When you run above program, you will get below output:

That’s all about Sliding Window Maximum in java.

If you want to practice data structure and algorithm programs, you can go through Java coding interview questions.

In this post, we will see how to count number of occurrences (or frequency) of each element in a sorted array

Problem

Given a Sorted Array of integers containing duplicates. Find the frequency of every unique element present in the array.
Frequency is defined as the number of occurrence of any element in the array.

For example :

Solution

Lets first Discuss the basic divide and conquer strategy to solve this problem.
we divide the array into two halves every time our function is called splitting our problem into half every time giving rise to a worst time complexity of O(log(n)).

Our array is not actually divided into halves, but we keep two pointers start and end representing some portion of array to work with and this is how our array is virtually split.

We know that our array is already sorted. So we can conclude that,

• if the elements at start pointer and end pointer are equal to the element whose frequency is to be calculated, this means that whole virtual array contains that element only and hence we directly add (end-start+1) to our frequency count.
• If this is not the case, we recur for the two halves of the array and in post order we will add the calls of these two result to make our final frequency count result.

Now, This whole algorithm was for finding the frequency of one element in the array.
For finding the frequency of every element this function needs to be called every time.
Hence the overall worst time complexity for solving this problem with this algorithm will be
O(n*log(n)).

package org.arpit.java2blog;

import java.util.HashSet;
import java.util.Scanner;

public class FreqOfEachElems {

    public static void main(String[] args) {

        Scanner scn = new Scanner(System.in);
        int[] arr = new int[scn.nextInt()];

        for (int i = 0; i < arr.length; i++) {
            arr[i] = scn.nextInt();
        }

        HashSet<Integer> processed = new HashSet();
        for (int val : arr) {
            if (!processed.contains(val)) {
                System.out.println("Frequency of " + val + " is : " + 
                        solveRecursive(0, arr.length - 1, arr, val));
                processed.add(val);
            }
        }

    }

    public static int solveRecursive(int start, int end, int[] arr, int element) {
        /* if start is greater than n, we need to return because this 
          represent a subarray of negative size.*/
        if (start > end) {
            return 0;
        }

        /* this means that the size of the virtual subarray is one, 
         * and it has only single element. */
        if (start == end) {
            /* now if this single element is equal to the element 
             * whose frequency we are finding out, 
             * then it will contribute one for its total frequency 
             * in the whole array. */
            if (arr[start] == element && arr[end] == element) {
                return 1;
            } else {
                return 0;
            }
        }

        /* if the virtual subarray is of size greater than one, 
         * and the elements at start and at the end are equal, 
         * this means that whole array consists of 
         * that element only, as the array 
         * we are working on is already sorted.*/
        if (arr[start] == element && arr[end] == element) {
            return (end - start + 1);
        }

        int mid = (start + end) / 2;
        /* call for left side virtual subarray */
        int leftResult = solveRecursive(start, mid, arr, element);

        /* call for right side virtual subarray.*/
        int rightResult = solveRecursive(mid + 1, end, arr, element);

        /* our result will be calculated in postorder, 
         * which will be left side result 
         * plus the right side sum.*/
        return leftResult + rightResult;
    }
}

EFFICIENT APPROACH:

There is an iterative and even efficient approach also which solves the problem in single parse in linear time i.e. O(n).

What we can do is, we keep a frequency array and loop through the array, and every time we find any element we go to the frequency array and add 1 to the previous frequency of that element in the frequency array.
After the loop ends, we are left with an array where at every index their frequency in the original array is present.
And also the biggest plus point along with its efficiency is, We don’t necessarily need the array to be sorted.

For eg :
Consider an Array and its frequency array,
int[] arr = {5,4,3,2,4,3,2,5,5};
int[] freqArr = {0,0,0,0,0,0};
the frequency array after the loop ends will look like,
int[] freqArr = {0,0,2,2,1,3};

In this frequency array, at every i th index, the frequency of  i in actual array is sitting.

By this time, we have already known the shortcomings of this approach,
Yes, this approach will not be effective when the input array contains negative numbers or numbers greater than 10^9.
Because we do not have any negative indices and an array of size 10^9 is not possible.
so for handling that, we need to use Hashmap where we store the element-frequency pair as the key-value pair in hashmap.

package org.arpit.java2blog;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Scanner;

public class FreqOfEachElems {

    public static void main(String[] args) {

        Scanner scn = new Scanner(System.in);
        int[] arr = new int[scn.nextInt()];

        for (int i = 0; i < arr.length; i++) {
            arr[i] = scn.nextInt();
        }

        System.out.print("arr[]: {");
        for (int i = 0; i < arr.length; i++) {
            System.out.print(" "+arr[i]);
        }

        System.out.println(" }");
        HashMap<Integer, Integer> freqMap = solveIterative(arr);

        for(int val : freqMap.keySet())
        {
            System.out.println("Frequency of " + val + " is : " + freqMap.get(val));
        }

    }

    public static HashMap<Integer, Integer> solveIterative(int[] arr)
    {
        HashMap<Integer, Integer> freqMap = new HashMap<>();

        /* iterate through the array for contributing +1 
         * as a frequency of that element, every time it is encountered.*/
        for(int val : arr)
        {
            if(!freqMap.containsKey(val))
            {
                /* if hashmap doesnt contains that element, 
                 * this means this is the first time the element is encountered,
                 * therefor freq of this element will be one for now.*/
                freqMap.put(val, 1);
            }
            else {
                /* if hashmap contains this element, 
                 * so now its updated frequency will be its past frequency + 1.
                 */
                freqMap.put(val, freqMap.get(val)+1);
            }
        }   
        return freqMap;
    }
}

When you run above program, you will get below output

Comment in case of any doubt or edit. Happy Learning

If you want to practice data structure and algorithm programs, you can go through Java coding interview questions.

In this post, we will see how to find subarrays with given sum in an array.

Problem

Given an Array of non negative Integers and a number. You need to print all the starting and ending indices of Subarrays having their sum equal to the given integer.
For Example :-

Explanation :
[3, 6]
[9],
[9,0]
These all are the subarrays with their sum equal to 9.

Solution

Naive Method:
The basic brute force approach to this problem would be generating all the subarrays of the given array, then loop through the generated subarray and calculate the sum and if this sum is equal to the given sum then printing this subarray as it is the part of our solution.

Now we know, An Array with n elements has n*(n+1)/2 subarrays.
HOW?
Consider an array,

Now,
Total subarrays = subarrays starting with 0th idx + subarrays starting with 1st idx +
subarrays starting with 2nd idx + . . . + subarrays starting with nth idx

Sn = n + (n-1) + (n-2) + (n-3) + ... + 1

Sn = n(n+1)/2

There, generating all the subarrays and calculating the answer will cost us the worst time complexity of O(n(n+1)/2) which is of the order O(n^2).

package Arrays;

import java.util.Scanner;

public class targetsumSubarr {

    public static void main(String[] args) {

        Scanner scn = new Scanner(System.in);
        int[] arr = new int[scn.nextInt()];
        int target = scn.nextInt();

        for (int i = 0; i < arr.length; i++) {
            arr[i] = scn.nextInt();
        }

        solve(arr, target);

    }

    public static void solve(int[] arr, int target)
    {
        for(int start = 0; start < arr.length; start++)
        {
                 // initialize the sum of the current subarray to 0.
            int currSum = 0;
            for(int end = start; end < arr.length; end++)
            {
                // add every element of the current subarray
                // to the current running sum.
                currSum += arr[end];

               // print the starting and ending indices once we get
               // subarray with given sum
                if(currSum == target)
                {
                     System.out.println("starting index : " +
                                 start + ", " + "Ending index : " + end);

                }

            }
        }
    }

}

Efficient Approach:

We can solve this problem in linear time i.e. in O(n) as the worst time complexity.

We can maintain two pointers, start and end pointers which basically represents a subarray and also we have to take a variable which stores the current sum of the subarray starting from start pointer and ending at end pointer.

•  we keep on incrementing end pointer while adding the element in the current sum until we reach a point where our current running sum is more than required target sum, this basically means that the current subarray whose sum we’ve calculated is not the right answer.
• So now we alter our subarray by moving the start pointer, that is shortening the subarray and hence the current sum in the hope that we achieve the current sum equal to the required target sum.
• At every point we check if our current sum is equal to target sum or not, if this is the case we print our pointers.
• So basically we are altering the subarray by increasing start and end pointers and changing the current sum depending on its value as compared to target sum.

package org.arpit.java2blog;

import java.util.Scanner;

public class TargetsumSubarr {

    public static void main(String[] args) {

        Scanner scn = new Scanner(System.in);
        int[] arr = new int[scn.nextInt()];
        int target = scn.nextInt();

        for (int i = 0; i < arr.length; i++) {
            arr[i] = scn.nextInt();
        }

        System.out.print("arr[]: {");
        for (int i = 0; i < arr.length; i++) {
            System.out.print(" "+arr[i]);
        }

        System.out.println(" }");
        solveEfficient(arr, target);

    }

    public static void solveEfficient(int[] arr, int target) {
        int start = 0, end = 0;

        int currSum = 0;

        while (start < arr.length && end <= arr.length) {
            if (currSum == target) {

                /* as the currSum is equal to target sum, print the 
                 * result with end as end-1.
                 *  because when we added the element at end we
                 *  increased the pointer there only,
                 *  so now we need to subtract 1 because the 
                 *  subarray constituting that sum has
                 *   its last pointer one index where end is currently at.
                 */

                System.out.println("starting index : " + start + ", " + 
                        "Ending index : " + (int) (end - 1));

                if (end <= arr.length - 1) {
                    currSum += arr[end];
                }
                end++;

            }

            else {
                /* if the currSum becomes more than required, 
                 * we keep on subtracting the start element
                 * until it is less than or equal to 
                 required target sum. */
                if (currSum > target) {
                    currSum -= arr[start];
                    start++;
                } else {
                    /* we add the last element to our
                     * currSum until our 
                     * sum becomes greater than or
                     * equal to target sum.
                     */
                    if (end <= arr.length - 1) {
                        currSum += arr[end];
                    }
                    end++;
                }
            }
        }
    }
}

When you run above program, you will get below output:

Doubts? Edits? Suggestions? Comment below. Happy Learning

If you want to practice data structure and algorithm programs, you can go through Java coding interview questions.

In this post, we will see how to count number of 1’s in sorted binary array.

Problem

Print number of 1’s in a given sorted Binary Array.
For eg:-

Solution

The Naive solution to solve this problem would be looping in the array and keep a count of 1’s occurring in the array.
But as the array is sorted we can stop at the very first one encountered, because as the array is sorted we can be sure that the element after first one would all be greater than or equal to ones, but as our array contains zeroes and ones only, therefore all elements after first one would be one. So our answer would be (array.length – currentPointer). This will handle all the test cases and works in linear O(n) time.

package Arrays;

import java.util.Scanner;

public class num1sInsortedbinaryArray {

    public static void main(String[] args) {

        Scanner scn = new Scanner(System.in);
        int[] arr = new int[scn.nextInt()];

        for (int i = 0; i < arr.length; i++) {
            arr[i] = scn.nextInt();
        }

        System.out.println(solve(arr));

    }

    public static int solve(int[] arr) {
        int currPointer = 0;

        while (currPointer < arr.length) {
            if (arr[currPointer] == 1) {
            // as we have found our first one, we will stop here and 
                        // result would be (arr.length-currPinter)
                break;
            }
            // we will keep on increasing currPoniter as long as we are 
                        //encountering zeroes
            currPointer++;
        }

        return (arr.length - currPointer);

    }
}

We can still solve the problem more efficiently in logarithmic time i.e. with a worst time complexity of O(log n).

Efficient Approach :

We can use divide and conquer approach, and move recursively at every step dividing the array into two subarrays virtually by keeping our start and end pointers.

1.  If the element at end pointer of a subarray is zero this means that all the elements in that array would be zeroes and we know the array is already sorted.
2. What if the first element that is the value at start pointer of the array? this means that all the elements in that subarray are ones again keeping in mind that array is sorted.

Now let’s discuss the time complexity.
At every call we are basically dividing the number of elements to work upon into two halves.
Initially we had N elements, then N/2, then N/4 and so on until we have one element left to work with.

if we denote T(n) for the time taken to process n elements.
Mathematically, we can write the equations as:

Say we have x such equations and as we move up in equations, number of elements are getting doubled, so eventually,
n = 2^x
taking log on both sides,
x = log(n) {to the base 2}
Hence the complexity of our algorithm comes out to be O(log(n)).

package org.ayush.java2blog;
import java.util.Scanner;

public class Num1sInSortedBinaryArray {

    public static void main(String[] args) {

        Scanner scn = new Scanner(System.in);
        int[] arr = new int[scn.nextInt()];

        for (int i = 0; i < arr.length; i++) {
            arr[i] = scn.nextInt();
        }

        System.out.print("arr[]: {");
        for (int i = 0; i < arr.length; i++) {
            System.out.print(" "+arr[i]);
        }

        System.out.println(" }");

        System.out.println("Number of 1 in array :"+solveEfficient(0, arr.length-1, arr));

    }

    public static int solveEfficient(int start, int end, int[] arr) {
        if (arr[start] == 1) {
        // start elem is one, hence all other elements will be one in 
                // virtual subarr.
            return end - start + 1;
        }

        if (arr[end] == 0) {
             // end elem is zero this means, all previous elements of 
                 //subarr will be zeroes.
            return 0;
        }

        int mid = (start + end) / 2;
        int leftResult = solveEfficient(start, mid, arr);
        int rightResult = solveEfficient(mid + 1, end, arr);
        // divide the array into two virtual subHalves
        return leftResult + rightResult;

    }
}

When you run above program, you will get below output

That’s all about how to Count 1’s in sorted Binary Array
Comment in case of any doubt or edit. Happy Learning