32. Minimum swaps to make elements<k together

32. Minimum swaps to make elements<k together

Problem link :- cllick here

package programs;

import java.util.*;

public class Array__32
{

	/*
	    1)We will find the number of elements <= k
	    2)We iterate through the array and react on for elements <=k
	              if we find a element <=k 
	                             we will find the maximum number of consecutive elements <=k
	                             we know how many elements are <=k using that we will find 
	                             how many elements to swap if we want to bring all elements in that position(around i)
	     we find minimum of these values since we may get more than one value(values that we get in step-2)
	*/
	static int minimumSwaps(int arr[], int n, int k)
	{
		int m = 0;  //to store the number of elements <= k
		for(int i=0; i<n; i++)
		{
			if(arr[i] <= k)
				m++;
		}
		
		
		int min_swaps = Integer.MAX_VALUE;      //our result
		int count = 0;
		for(int i=0; i<n; i++)
		{
			if(arr[i] <= k)
			{
				count++;
				/*
				     swaps we must do to bring all the remaining here is 
				              m - count     (because count is number of elements 
				                                        <= k present here together,
				                                        we want to bring the remaining elements )
				*/
				min_swaps = Math.min(min_swaps,  m-count);
			}
			/*
			    initializing count to zero again because if we have come to else part means
			    some element >k has interrupted the continuity of the elements
			*/
			else
				count = 0;
		}
		
		return min_swaps;
	}
	
	static int minSwaps(int arr[], int n, int k)
	{
		/*
		     good  ->  no of elements that is <=k  
		     bad    ->  no of elements that is   >k
		 */
		// 	APPROACH ---->  SLIDING WINDOW (necessary)
		int good, bad, final_bad, i;
		good = 0;
		bad = 0;
		
		for(i=0; i<n; i++)
		{
			if(arr[i] <= k)
				good++;
		}
		
		//First window(0  to  good-1)
		for(i=0; i<=good-1; i++)
		{
			if(arr[i] > k)
				bad++;
		}
		final_bad = bad;
		
		for(i=1; i+good-1<n; i++)
		{
			if(arr[i-1]  > k)	//checking if left element from
				bad--;	       // window is a bad element
			
			if(arr[i+good-1] > k)     	//checking if added element to
				bad++;			//window is a bad element
			
			final_bad = Math.min(bad, final_bad);
		}
		return final_bad;
	}
	
	public static void main(String[] args)
	{
		int n, i, k, ans;
		
		Scanner s = new Scanner(System.in);
		System.out.print("Enter the size of the array : ");
		n = s.nextInt();
		int array[] = new int[n];
		System.out.println("Enter the elements of the array : ");
		for(i=0; i<n; i++)
			array[i] = s.nextInt();
		System.out.print("Enter a positive integer : ");
		k = s.nextInt();
		
		System.out.println("Given Array : ");
		printArray(array);
		
		ans = minSwaps(array, n, k);
		System.out.println("\n\nMinimum swaps requred is : " + ans);
	}

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

Time complexity :- O(n)
Space complexity :- O(1)