Array
Last updated
Was this helpful?
Last updated
Was this helpful?
Element in array is identified by index. The size is fixed => when array is full not easy to add an element.
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
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--;
}
}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);
}
}
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:
Find the size of the window required
Compute the result for 1st window, i.e. from the start of the data structure
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 :
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.
Then we will graze linearly over the array till it reaches the end and simultaneously keep track of the maximum sum.
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.
// 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));
}
}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./*
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
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;
}
}// 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;
}
}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
