Array

Problem Solving

  • Objective :
    • Should be easy to revise
    • Algorithm
    • Possible Edge cases
    • common use-case learning

Arrays Questions

  1. Remove Duplicates from Sorted Array
  2. Find the duplicate in an array of N+1 integers.
  3. Sort an array of 0’s 1’s 2’s without using extra space or sorting algo
  4. Find the repeating and missing numbers
  5. Merge Sorted Arrays
  6. Equilibrium Index of an array
  7. Find row number of a binary matrix having maximum number of 1s
  8. Set Matrix Zeros
  9. Pascal Triangle
  10. Next Permutation
  11. Inversion of Array (Using Merge Sort)
  12. Stock Buy and Sell
  13. Rotate Matrix
  14. Search in a 2D matrix
  15. Pow(X,n)
  16. Majority Element (>N/2 times)
  17. Majority Element (>N/3 times)
  18. Grid Unique Paths
  19. Reverse Pairs (Leetcode)
  20. Max Length Sub-array
    1. brute-force
    2. hash-map

1.Remove Duplicates from Sorted Array

Problem Description :

Given an integer array nums sorted in non-decreasing order, remove the duplicates in-place such that each unique element appears only once. The relative order of the elements should be kept the same. Then return the number of unique elements in nums.

Approach 1: Using Hashset

  1. Algorithm
    1. use a hash-set to detect unique -put the unique in new array
    2. place new array elements in old to make changes in old array
  2. Challenge[Problem|coding] current implementation? -NA
  3. Shortcomings
    • extra space for set
    • Two iterations for populating hs & reassigning old array from new.
//Approach-1
  int removeDuplicateAndUnique(int[] nums) {
     int newa[] = new int[nums.length];
     int unique = 0, j = 0;
     HashSet < Integer > hs = new HashSet < > ();
     for (int i = 0; i <= nums.length - 1; i++) {
         if (hs.add(nums[i])) {
             unique++;
             newa[j++] = nums[i];

         }
     }
     for (int i = 0; i <= newa.length - 1; i++) {
         nums[i] = newa[i];
     }
     return unique;
 }

Approach 2: In-place

  1. Algorithm
    1. Note: it’s a sorted array –
      1. keep a tracker of unique-element position
      2. iterate over array & once you have different element – place it at position of tracker and increment the tracker position
  2. Notes:
    • For possible ArrayIndexOutOfBound senarious – compare current element to previous element – that way you intrinsically handled the AIOB scenarios.
    • in this solution – the unique elements appear first and after that numbers are as it is – i.e array length doesn’t change.
    public int removeDuplicates(int[] nums) {
        int uniqueElemntPosition = 1;
        int len = nums.length;
        if (len <= 1) {
            return len;
        }
        if (len == 2) {
            if (nums[0] == nums[1]) {
                return 1;
            } else {
                return len;
            }
        }
        for (int i = 2; i < len; i++) {
            if (nums[i] != nums[i - 1]) {
                // place at unqinue elemtn postition,increase the unqieposit
                nums[uniqueElemntPosition++] = nums[i];

            }
        }

        return uniqueElemntPosition + 1;
    }

2.Find the duplicate in an array of N+1 integers.

Problem Description :

Given an array of integers nums containing n + 1 integers where each integer is in the range [1, n] inclusive.There is only one repeated number in nums, return this repeated number.You must solve the problem without modifying the array nums and uses only constant extra space.

Approach 1:Using Hashset

  1. Algorithm
    • use a hash-set to detect unique -put the unique in new array
  2. Challenge[Problem|coding] current implementation? NA
  3. Shortcoming
    • O(n) extra space for HS

Approach 2:Array Setter with marker

Approach 3:Fischer cycle detection (2 pointer – fast and slow)

3.Sort an array of 0’s 1’s 2’s without using extra space or sorting algo

Problem Description :

Given an array nums with n objects colored red, white, or blue, sort them in-place so that objects of the same color are adjacent, with the colors in the order red, white, and blue.We will use the integers 0, 1, and 2 to represent the color red, white, and blue, respectively.You must solve this problem without using the library’s sort function.

Approach 1: Occurrence count using HM and populate array corresponding to counts

  1. Algorithm
    • count occurrence of 0,1,2
    • set the index to the number of occurrence
  2. Challenge[Problem|coding] current implementation?
    • using Stream to set the map : error: “cant do put(int[],int) having definatin put(int,int) – Q- does stream make source a array of int?
      • Error: Stream.of(nums).map(x->x)forEach(x->{colorCOunt.put(x,colorCOunt.getOrDefault(x,0)+1);});
  3. Shortcoming
    • count and storage of elements extra TC- O(1),SC- O(n)
    • setting the N colors is inplace,extra loop used.
    public void sortColors(int[] nums) {
        Map < Integer, Integer > colorCOunt = new HashMap < > ();
        for (int x: nums) {
            colorCOunt.put(x, colorCOunt.getOrDefault(x, 0) + 1);
        }
        int i=0,val=0;
        for(int key:colorCOunt.keySet()){
            val+=colorCOunt.get(key);
            while(i<val){
                 nums[i]=key;
                 i++;
            }
        }

    }

Approach 2: Dutch National Flag Algorithm

Algorithm:

  1. Maintain three pointers low and mid at 0, high at end.
  2. Iterate mid & whenever there is 0 put that to extreme left by swapping it with low and increment low and mid.
  3. Whenever there is 1 just let it be there and increment mid.
  4. whenever there is 2 put that to extreme right by swapping nums[mid] with nums[high].
//Todo: in next iteration

4.Find the repeating and missing numbers

Problem Statement :

You are given a read-only array of N integers with values also in the range [1, N] both inclusive. Each integer appears exactly once except A which appears twice and B which is missing. The task is to find the repeating and missing numbers A and B where A repeats twice and B is missing.

Approach 1:Sort the array and count

  1. Algorithm
    • sort the arrray
    • linear iteration to check if number missing or repeated
  2. Challenge[Problem|coding] current implementation? NA
  3. Shortcoming
    • Needed sorting to find the occurrence – can it be done without sorting?

Approach 2: Occurrence count using HM

  1. Algorithm
    • count occurance
    • one having 2 or 0 occ is the resultant
  2. Challenge[Problem|coding] current implementation? NA
  3. Shortcoming
    • Extra space and iteration to find the occurrence

5.Merge Sorted Array

Problem Description :

You are given two integer arrays nums1 and nums2, sorted in non-decreasing order, and two integers m and n, representing the number of elements in nums1 and nums2 respectively.

Merge nums1 and nums2 into a single array sorted in non-decreasing order.

The final sorted array should not be returned by the function, but instead be stored inside the array nums1. To accommodate this, nums1 has a length of m + n, where the first m elements denote the elements that should be merged, and the last n elements are set to 0 and should be ignored. nums2 has a length of n.

Approach 1: count occurrence since sorted place lowest first

  1. Algorithm
    • count occurrence of 0,1,2
    • set the index to the number of occurrence
  2. Challenge[Problem|coding] current implementation?
    • using Stream to set the map : error: “cant do put(int[],int) having definatin put(int,int) – Q- does stream make source a array of int?
      • Error: Stream.of(nums).map(x->x)forEach(x->{colorCount.put(x,colorCount.getOrDefault(x,0)+1);});
  3. Shortcoming
    • count and storage of elements extra TC- O(1),SC- O(n)
    • setting the N colours is in-place, extra loop used.

Approach 2: merge in largest sorted array

  1. Algorithm
    • resultant array size will be sum of size of 2 arrays i.e : pmerge=(p1+p2) -1
    • Since in-place merge has to be done – iterate over smaller array from end
    • place the elements in nums1-1st array from end i.e pmerge – bigger elemt being placed first at end
    • reduce the position ///once element placed at pmerge index.
  2. Challenge[Problem|coding] current implementation?
  3. Shortcoming

  public void merge(int[] nums1, int m, int[] nums2, int n) {
        int pos1 = m - 1;
        int pos2 = n - 1;
        int pMerge = m + n - 1;
        
        while (pos2 >= 0) {// element exists in nums2
            if (pos1 >= 0 && nums1[pos1] > nums2[pos2]) {
                nums1[pMerge--] = nums1[pos1--];
            } else {
                nums1[pMerge--] = nums2[pos2--];
            }
        }
    }

6.Merge Intervals

Problem Description :

Given an array of intervals where intervals[i] = [starti, endi], merge all overlapping intervals, and return an array of the non-overlapping intervals that cover all the intervals in the input.

Example 1:Input: intervals = [[1,3],[2,6],[8,10],[15,18]] Output: [[1,6],[8,10],[15,18]] Explanation: Since intervals [1,3] and [2,6] overlap, merge them into [1,6].

Approach 1: compare each interval with other

  1. Algorithm
    • pick an interval compare with others
  2. Challenge[Problem|coding] current implementation?
    • resultant array is or flxible size – use list
  3. Shortcoming
    • count and storage of elements extra TC- O(N2)

Approach 2: sort the intervals based on staring point and then compare and add to result

  1. Algorithm
    • sort based on starting point
    • compare the current interval starting point to previous interval end point – to check if overlapping
      1. for overlapping -chane the prevInterval end-point
      2. for non overlappin- add the interval to resltant
  2. Challenge[Problem|coding] current implementation?
    • sorting based on starting point
    • converting back to array
    public int[][] merge(int[][] intervals) {
 
        Arrays.sort(intervals,Comparator.comparingInt(i->i[0]));
        List<int[]> result=new LinkedList<>();
   int[] prevInterval=intervals[0];     
result.add(prevInterval);
for(int[] currentInterval:intervals){
    if(currentInterval[0]<=prevInterval[1]){
        //overlapping intervals hadnlinf
        prevInterval[1]=Math.max(prevInterval[1],currentInterval[1]);
    }else{
        prevInterval=currentInterval;
        //non-overlappin intervals
        result.add(currentInterval);
    }}
        return result.toArray(new int[result.size()][]);
    }
  1. Equilibrium index of an array

Asked by hashedIN

Description of Question –

Equilibrium index of an array is an index such that the sum of elements at lower indexes is equal to the sum of elements at higher indexes.

For example, in an array A: 

Example : 

Input: A[] = {-7, 1, 5, 2, -4, 3, 0} 
Output: 3 
3 is an equilibrium index, because: 
A[0] + A[1] + A[2] = A[4] + A[5] + A[6]

Input: A[] = {1, 2, 3} 
Output: -1

Solution -Brute-force solution

// Java program to find equilibrium
// index of an array

class EquilibriumIndex {
	int equilibrium(int arr[], int n)
	{
		int i, j;
		int leftsum, rightsum;

		/* Check for indexes one by one until
		an equilibrium index is found */
		for (i = 0; i < n; ++i) {

			/* get left sum */
			leftsum = 0;
			for (j = 0; j < i; j++)
				leftsum += arr[j];

			/* get right sum */
			rightsum = 0;
			for (j = i + 1; j < n; j++)
				rightsum += arr[j];

			/* if leftsum and rightsum are same,
			then we are done */
			if (leftsum == rightsum)
				return i;
		}

		/* return -1 if no equilibrium index is found */
		return -1;
	}
	// Driver code
	public static void main(String[] args)
	{
		EquilibriumIndex equi = new EquilibriumIndex();
		int arr[] = { -7, 1, 5, 2, -4, 3, 0 };
		int arr_size = arr.length;
		System.out.println(equi.equilibrium(arr, arr_size));
	}
}

Time Complexity: O(n^2)

Solution -Space time Tradeoff

This is a quite simple and straightforward method. The idea is to take the prefix sum of the array twice. Once from the front end of array and another from the back end of array.

After taking both prefix sums run a loop and check for some i if both the prefix sum from one array is equal to prefix sum from the second array then that point can be considered as the Equilibrium point.

// Java program to find equilibrium
// index of an array
class Solution{

static int equilibrium(int a[], int n)
{
	if (n == 1)
		return (0);
	
	int[] front = new int[n];
	int[] back = new int[n];

	// Taking the prefixsum from front end array
	for (int i = 0; i < n; i++)
	{
		if (i != 0)
		{
			front[i] = front[i - 1] + a[i];
		}
		else
		{
			front[i] = a[i];
		}
	}

	// Taking the prefixsum from back end of array
	for (int i = n - 1; i > 0; i--)
	{
		if (i <= n - 2)
		{
			back[i] = back[i + 1] + a[i];
		}
		else
		{
			back[i] = a[i];
		}
	}
	
	// Checking for equilibrium index by
	//compairing front and back sums
	for(int i = 0; i < n; i++)
	{
		if (front[i] == back[i])
		{
			return i;
		}
	}
	
	// If no equilibrium index found,then return -1
	return -1;
}

// Driver code
public static void main(String[] args)
{
	int arr[] = { -7, 1, 5, 2, -4, 3, 0 };
	int arr_size = arr.length;
	
	System.out.println("First Point of equilibrium " +
					"is at index " +
					equilibrium(arr, arr_size));
}
}
  • Time Complexity: O(N)
  • Space Complexity: O(N)
  1. Find row number of a binary matrix having maximum number of 1s

https://www.geeksforgeeks.org/find-row-number-binary-matrix-maximum-number-1s/

https://www.geeksforgeeks.org/find-the-row-with-maximum-number-1s/

  1. Find the repeating and missing numbers

Problem Statement : Set Matrix Zeroes

Given an m x n integer matrix matrix, if an element is 0, set its entire row and column to 0‘s.

You must do it in-place

Approach 1:mark the elements to be set to 0 with an identifer ,and reset the itenfiter to 0

  1. Algorithm
    • sort the arrray
    • linear iteration to check if number missing or repeated
  2. Challenge[Problem|coding] current implementation? NA
  3. Shortcoming
    • Needed sorting to find the occurrence – can it be done without sorting?

Approach 2: Take 2 identifers – sets once for rowsToBeSetToZero and another for colsToBeSetToZero

  1. Algorithm
    • count occurance
    • one having 2 or 0 occ is the resultant
  2. Challenge[Problem|coding] current implementation? NA
  3. Shortcoming
    • Extra space and iteration to find the occurrence

M

Pages: Page 1, Page 2

Published by

Unknown's avatar

sevanand yadav

software engineer working as web developer having specialization in spring MVC with mysql,hibernate

Leave a comment