Array

Array

Element in array is identified by index. The size is fixed => when array is full not easy to add an element.

Common Array algorithms

• Using Multi-Dimensional Arrays Multi-dimensional arrays are a common way to add complexity to array problems in an interview. It’s critical that you be comfortable applying all the common array operations in multiple dimensions

• Using Multiple Pointers While not exactly a singular algorithm, traversing an array with multiple pointers simultaneously is a very important technique

Merge arrays

Given 2 sorted arrays, A and B, where A is long enough to hold the contents of A and B, write a function to copy the contents of B into A without using any buffer or additional memory.

A = {1,3,5,0,0,0}
B = {2,4,6}
mergeArrays(A, B)
A = {1,2,3,4,5,6}

Solution

A = {1,3,5,0,0,0}
         ^     ^      
       aIndex  mergeIndex  
B = {2,4,6}
         ^
       bIndex  

We are traversing starting from the tail of A array comparing and choosing the largest value among A tail and B tail.

Important is the second while loop, which makes sure that all values of B are ending up in A.

public void mergeArrays(int[] a, int[] b, int aLength, int bLength) {
    if (aLength + bLength > a.length) throw new IllegalArgumentException();

    int aIndex = aLength - 1;
    int bIndex = bLength - 1;
    int mergeIndex = aLength + bLength - 1;

    while (aIndex >= 0 && bIndex >= 0) {
        if (a[aIndex] > b[bIndex]) {
            a[mergeIndex] = a[aIndex];
            aIndex--;
        } else {
            a[mergeIndex] = b[bIndex];
            bIndex--;
        }

        mergeIndex--;
    }

    while (bIndex >= 0) {
        a[mergeIndex] = b[bIndex];
        bIndex--;
        mergeIndex--;
    }
}

Find duplicates in array

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class FindDuplicates {
	
	/*
	https://www.youtube.com/watch?v=GeHOlt_QYz8
	
	Given an array of integers where each value 1 <= x <= len(array),
	write a function that finds all the duplicates in the array.
	
	dups([1, 2, 3])    = []
	dups([1, 2, 2])    = [2]
	dups([3, 3, 3])    = [3]
	dups([2, 1, 2, 1]) = [1, 2]

	Possible solutions can be:
	1. Bruteforce: O(N^2)	this is not an option
	
	2. To have an auxiliary Set, store values in this Set and then compare each i-th
	value from array with values in Set:
		complexity: O(N)
		space: O(N) for auxiliary Set
		
	3. To have an auxiliary Map, and keys will be a unique values in the array,
	and map values will be number of occurrences of particular value in the array
		complexity: O(N)
		space: O(N) for auxiliary Map
		
	4. Sort array initially and then iterate over sorted array
		complexity: O(NlogN)
		space: O(1)
		
	5. 	Encode the information in the array, which will help to identify, whether the
	value was already "met". Important condition of this solution is that values in the arrays are 1 <= x <= len(array).
	Below code displays the logic of current solution:
	 */
	public static List<Integer> findAllDuplicates(int[] array) {
		Set<Integer> resultSet = new HashSet<>();
		
		for (int i = 0; i < array.length; i++) {
			int index = Math.abs(array[i]) - 1;
			if (array[index] < 0) {
				resultSet.add(Math.abs(array[i]));
			} else {
				array[index] = -array[index];
			}
		}
		
		// This is just to return the array in the initial state, in case some values became negative
		// This is basically a "nice" behaviour to leave the data in the state it came into the method
		for (int i = 0; i < array.length; i++) {
			array[i] = Math.abs(array[i]);
		}
		return new ArrayList<>(resultSet);
	}
	
}

• Sliding Windows This is a super useful technique used for finding subarrays that match specific criteria. It also demonstrates a lot of other relevant techniques such as using multiple pointers in an array

Sliding window (find max sum of subarray of size k)

The use of the Sliding Window technique can be done in a very specific scenario, where the size of the window for computation is fixed throughout the complete nested loop. Only then the time complexity can be reduced.

How to use Sliding Window Technique?

The general use of the Sliding window technique can be demonstrated as follows:

1. Find the size of the window required

2. Compute the result for 1st window, i.e. from the start of the data structure

3. Then use a loop to slide the window by 1, and keep computing the result window by window.

How to Know, Where we use the Sliding Window?

To know, Where we use the Sliding Window then we remember the following terms which is mentioned below:

Array, String, Sub Array, Sub String, Largest Sum, Maximum Sum, Minimum Sum

Examples to illustrate the use of the Sliding window technique

Example: Given an array of integers of size ‘n’, Our aim is to calculate the maximum sum of ‘k’ consecutive elements in the array.

Input : arr[] = {100, 200, 300, 400}, k = 2 Output : 700

Input : arr[] = {1, 4, 2, 10, 23, 3, 1, 0, 20}, k = 4 Output : 39 We get maximum sum by adding subarray {4, 2, 10, 23} of size 4.

Input : arr[] = {2, 3}, k = 3 Output : Invalid There is no subarray of size 3 as size of whole array is 2.

Naive Approach: So, let’s analyze the problem with Brute Force Approach. We start with the first index and sum till the kth element. We do it for all possible consecutive blocks or groups of k elements. This method requires a nested for loop, the outer for loop starts with the starting element of the block of k elements, and the inner or the nested loop will add up till the kth element.

class GFG {
    // Returns maximum sum in
    // a subarray of size k.
    static int maxSum(int arr[], int n, int k)
    {
        // Initialize result
        int max_sum = Integer.MIN_VALUE;
 
        // Consider all blocks starting with i.
        for (int i = 0; i < n - k + 1; i++) {
            int current_sum = 0;
            for (int j = 0; j < k; j++)
                current_sum = current_sum + arr[i + j];
 
            // Update result if required.
            max_sum = Math.max(current_sum, max_sum);
        }
 
        return max_sum;
    }
 
    // Driver code
    public static void main(String[] args)
    {
        int arr[] = { 1, 4, 2, 10, 2, 3, 1, 0, 20 };
        int k = 4;
        int n = arr.length;
        System.out.println(maxSum(arr, n, k));
    }
}

Time complexity: O(k*n) as it contains two nested loops. Auxiliary Space: O(1)

Sliding Window Technique: The technique can be best understood with the window pane in the bus, considering a window of length n and the pane which is fixed in it of length k. Consider, initially the pane is at extreme left i.e., at 0 units from the left. Now, co-relate the window with array arr[] of size n and pane with current_sum of size k elements. Now, if we apply force on the window, it moves a unit distance ahead. The pane will cover the next k consecutive elements.

Applying the sliding window technique :

1. We compute the sum of the first k elements out of n terms using a linear loop and store the sum in variable window_sum.

2. Then we will graze linearly over the array till it reaches the end and simultaneously keep track of the maximum sum.

3. To get the current sum of a block of k elements just subtract the first element from the previous block and add the last element of the current block.

4. 

// Java code for
// O(n) solution for finding
// maximum sum of a subarray
// of size k
class GFG {

	// Returns maximum sum in
	// a subarray of size k.
	static int maxSum(int arr[], int n, int k)
	{
		// n must be greater
		if (n < k) {
			System.out.println("Invalid");
			return -1;
		}

		// Compute sum of first window of size k
		int max_sum = 0;
		for (int i = 0; i < k; i++)
			max_sum += arr[i];

		// Compute sums of remaining windows by
		// removing first element of previous
		// window and adding last element of
		// current window.
		int window_sum = max_sum;
		for (int i = k; i < n; i++) {
			window_sum += arr[i] - arr[i - k];
			max_sum = Math.max(max_sum, window_sum);
		}

		return max_sum;
	}

	// Driver code
	public static void main(String[] args)
	{
		int arr[] = { 1, 4, 2, 10, 2, 3, 1, 0, 20 };
		int k = 4;
		int n = arr.length;
		System.out.println(maxSum(arr, n, k));
	}
}

https://youtu.be/9-3BXsfrpbY?list=PLqM7alHXFySEQDk2MDfbwEdjd2svVJH9p

https://practice.geeksforgeeks.org/explore?page=2&category[]=sliding-window&sortBy=submissions

Sliding window (find subarray with sum of elements resulting to S)

Given an unsorted array A of size N that contains only positive integers, find a continuous sub-array that adds to a given number S and return the left and right index(1-based indexing) of that subarray.

In case of multiple subarrays, return the subarray indexes which come first on moving from left to right.

Note:- You have to return an ArrayList consisting of two elements left and right. In case no such subarray exists return an array consisting of element -1.

Example 1:

Input:
N = 5, S = 12
A[] = {1,2,3,7,5}
Output: 2 4
Explanation: The sum of elements 
from 2nd position to 4th position 
is 12.

Example 2:

Input:
N = 10, S = 15
A[] = {1,2,3,4,5,6,7,8,9,10}
Output: 1 5
Explanation: The sum of elements 
from 1st position to 5th position
is 15.

Video description of the solution

/*
   Given an unsorted array A of size N that contains only positive integers, 
   find a continuous sub-array that adds to a given number S and return the left and right index(1-based indexing) 
   of that subarray.
   In case of multiple subarrays, return the subarray indexes which come first on moving from left to right.
   
   Explanation: given {1,2,3,7,5} and sum 12
    
    ^          start
   {1,2,3,7,5}
    ^          last
    
    we are moving last pointer to the right
    currentSum = 1, is it more than 12? no => move last to the right
    
    ^          start
   {1,2,3,7,5}
      ^         last
   currentSum = 1+2 = 3, is it more than 12? no => move last to the right   
   
    ^          start
   {1,2,3,7,5}
        ^       last
   currentSum = 3+3 = 6, is it more than 12? no => move last to the right     
   
      ^         start
   {1,2,3,7,5}
          ^      last
   currentSum = 6+7 = 13, is it more than 12? yes => move last to the right, and move start to the right until
   currentSum becomes equal or less than 12   
   13 - 1 = 12
   
    */
   public static ArrayList<Integer> subarraySum(int[] arr, int n, int s) {
      int start = 0;
      int last = 0;
      int currentSum = 0;
      boolean flag = false;
      ArrayList<Integer> result = new ArrayList<>();
      
      for (int i = 0; i < n; i++) {
         currentSum += arr[i];
         
         if (currentSum >= s) {
            last = i;
            
            while (currentSum > s && start < last) {
               currentSum -= arr[start];
               start++;
            }
            
            if (currentSum == s) {
               result.add(start+1);
               result.add(last+1);
               flag = true;
               break;
            }
         }
      }
      
      if (!flag) {
         result.add(-1);
      }
      return result;
   }
}

• Sorting and Searching Arrays are a common format for data that we want to sort and search. Knowing how to do binary search as well as sort using common algorithms like Mergesort and Quicksort is a must

Find longest consecutive array

import java.util.HashSet;
import java.util.Set;

public class LongestConsecutiveArray {
   
   /*
   https://www.youtube.com/watch?v=1t-082mMScY
   
   Given an unsorted array, find the length of the longest sequence of consecutive numbers in the array.
   consecutive([4, 2, 1, 6, 5]) = 3, [4, 5, 6]
   consecutive([5, 5, 3, 1]) = 1, [1], [3], or [5]
   
   Approach 1: sort an array and then iterate over it once identifying the longest consecutive array
   complexity: O(N logN)
   space: 0(1)
   one drawback is that we change an input array, and then there is actually a faster solution
   
   Approach 2: Store array to HashSet to take away duplicates. By finding leftmost elements count consecutive arrays.
   [1, 2, 4, 5, 6] // it is sorted for better understanding
   start of the sequence = if the element i does not have a "neighbour" i-1
   We will find leftmost start of the sequence "1" and count consecutive till 2 (2 elements)
   We will find leftmost start of the sequence "4" and count consecutive till 5 (3 elements)
    */
   
   public static int longestConsecutive(int[] a) {
      Set<Integer> values = new HashSet<>();
      
      // store to set to avoid duplicates
      for (int i : a) {
         values.add(i);
      }
      
      int maxLength = 0;
      for (int i : values) {
         if (values.contains(i-1)) continue; // it means this is not a beginning of the sequence
         int length = 0;
         while (values.contains(i++)) length++; // count sequential part of the array
         maxLength = Math.max(maxLength, length);
      }
      return maxLength;
   }
}

Multi dimentional arrays

Matrix search

// https://www.byte-by-byte.com/matrixsearch/
// https://www.youtube.com/watch?v=bK7BCWICvpQ
public class SortedMatrixContainsValue {
	
	public static boolean contains(int[][] arr, int x) {
		if (arr.length == 0 || arr[0].length == 0) return false;
		
		int row = 0;
		int col = arr[0].length - 1;
		
		while (row < arr.length && col >=0) {
			if (arr[row][col] == x) return true;
			if (arr[row][col] < x) {
				row++;
			} else {
				col--;
			}
		}
		return false;
	}
}

Other challenges

Three sum

/*
https://www.byte-by-byte.com/threesum/ https://www.youtube.com/watch?v=-AMHUdZc9ss&t=1s


*/
public List<int[]> threeSum(int[] a) {

}