Arrays COPY Flashcards
Location of the next index depends on the data type that we use
True/false
true
Advantages of using arrays:
Arrays allow random access of elements. This makes accessing elements by their position faster.
Arrays have better cache locality that can make a pretty big difference in performance.
Programs with good locality tend to access the same set of data items over and over again from the upper levels of the memory hierarchy (i.e. cache) and thus run faster.
Time Complexity of this search operation in an array will be
O(N) in the worst case as we are checking every element of the array from 1st to last, so the number of operations is N.
Time complexity of insertion in an array ?
Time Complexity in worst case of this insertion operation can be linear i.e. O(N) as we might have to shift all of the elements by one place to the right.
O(1) for insertion at the end
what is sliding window technique
This technique shows how a nested for loop in few problems can be converted to single for loop and hence reducing the time complexity.
Let’s start with a problem for illustration where we can apply this technique:
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.
The Naive Approach to solve this problem is to calculate sum for each of the blocks of K consecutive elements and compare which block has the maximum sum possible. The time complexity of this approach will be O(n * k).
The above problem can be solved in Linear Time Complexity by using Window Sliding Technique by avoiding the overhead of calculating sum repeatedly for each block of k elements.
The technique can be best understood with the window pane in bus, consider 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 plane with current_sum of size k elements. Now, if we apply force on the window such that it moves a unit distance ahead. The pane will cover next k consecutive elements.
Consider an array arr[] = {5 , 2 , -1 , 0 , 3} and value of k = 3 and n = 5
Applying sliding window technique :
We compute the sum of 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 maximum sum.
To get the current sum of block of k elements just subtract the first element from the previous block and add the last element of the current block .
What is prefix sum array?
Prefix Sum Array: The prefix sum array of any array, arr[] is defined as an array of same size say, prefixSum[] such that the value at any index i in prefixSum[] is sum of all elements from indexes 0 to i in arr[].
That is,
prefixSum[i] = arr[0] + arr[1] + arr[2] + . . . . + arr[i]
for all 0 <= i <= N.
Examples:
Input : arr[] = {10, 20, 10, 5, 15}
Output : prefixSum[] = {10, 30, 40, 45, 60}
Explanation : While traversing the array, update
the element by adding it with its previous element.
prefixSum[0] = 10,
prefixSum[1] = prefixSum[0] + arr[1] = 30,
prefixSum[2] = prefixSum[1] + arr[2] = 40 and so on.
void fillPrefixSum(int arr[], int N, int prefixSum[])
{
prefixSum[0] = arr[0];
// Adding present element
// with previous element
for (int i = 1; i < N; i++)
prefixSum[i] = prefixSum[i-1] + arr[i];
}
Reverse an array using recursion
import java.util.Arrays;
class GfG {
// recursive function to reverse an array from l to r
static void reverseArrayRec(int[] arr, int l, int r) {
if (l >= r)
return;
// Swap the elements at the ends
int temp = arr[l];
arr[l] = arr[r];
arr[r] = temp;
// Recur for the remaining array
reverseArrayRec(arr, l + 1, r - 1);
}
// function to reverse an array
static void reverseArray(int[] arr) {
int n = arr.length;
reverseArrayRec(arr, 0, n - 1);
}
public static void main(String[] args) {
int[] arr = { 1, 4, 3, 2, 6, 5 };
reverseArray(arr);
for (int i = 0; i < arr.length; i++)
System.out.print(arr[i] + " ");
}
}brute force
Maximum and minimum of an array using minimum number of comparisons
import java.util.Arrays;
public class MinMaxFinder {
/**
* Finds the minimum element in an array of integers.
*
* @param A The input array.
* @param N The size of the array.
* @return The minimum element in the array.
*/
public static int setmini(int[] A, int N)
{
int mini = Integer.MAX_VALUE;
for (int i = 0; i < N; i++) {
if (A[i] < mini) {
mini = A[i];
}
}
return mini;
}
/**
* Finds the maximum element in an array of integers.
*
* @param A The input array.
* @param N The size of the array.
* @return The maximum element in the array.
*/
public static int setmaxi(int[] A, int N)
{
int maxi = Integer.MIN_VALUE;
for (int i = 0; i < N; i++) {
if (A[i] > maxi) {
maxi = A[i];
}
}
return maxi;
}
public static void main(String[] args)
{
int[] A = { 4, 9, 6, 5, 2, 3 };
int N = A.length;
System.out.println("Minimum element is: "
\+ setmini(A, N));
System.out.println("Maximum element is: "
\+ setmaxi(A, N));
}
}
Time Complexity: O(N)
Auxiliary Space: O(1)
Do by brute force: Given an array and a number k where k is smaller than the size of the array, we need to find the k’th smallest element in the given array. It is given that all array elements are distinct.
Examples:
Input: arr[] = {7, 10, 4, 3, 20, 15}
k = 3
Output: 7
Input: arr[] = {7, 10, 4, 3, 20, 15}
k = 4
Output: 10
Method 1 (Simple Solution)
A simple solution is to sort the given array using an O(N log N) sorting algorithm like Merge Sort, Heap Sort, etc, and return the element at index k-1 in the sorted array.
Time Complexity of this solution is O(N Log N)
// Function to return k'th smallest element in a given array
int kthSmallest(int arr[], int n, int k)
{
// Sort the given array
sort(arr, arr + n);
// Return k'th element in the sorted array
return arr[k - 1];
}
Given an array of size N containing only 0s, 1s, and 2s; sort the array in ascending order.
Example 1:
Input:
N = 5
arr[]= {0 2 1 2 0}
Output:
0 0 1 2 2
Explanation:
0s 1s and 2s are segregated
into ascending order.
Example 2:
Input:
N = 3
arr[] = {0 1 0}
Output:
0 0 1
Explanation:
0s 1s and 2s are segregated
into ascending order.
Your Task:You don't need to read input or print anything. Your task is to complete the function sort012() that takes an array arr and N as input parameters and sorts the array in-place.
Expected Time Complexity: O(N)Expected Auxiliary Space: O(1)
Constraints:1 <= N <= 10^60 <= A[i] <= 2Approach:The problem is similar to our old post Segregate 0s and 1s in an array, and both of these problems are variation of famous Dutch national flag problem.The problem was posed with three colours, here `0′, `1′ and `2′. The array is divided into four sections:
* a[1..Lo-1] zeroes (red)
* a[Lo..Mid-1] ones (white)
* a[Mid..Hi] unknown
* a[Hi+1..N] twos (blue)
* If the ith element is 0 then swap the element to the low range, thus shrinking the unknown range.
* Similarly, if the element is 1 then keep it as it is but shrink the unknown range.
* If the element is 2 then swap it with an element in high range.
Algorithm:
* Keep three indices low = 1, mid = 1 and high = N and there are four ranges,
1 to low (the range containing 0),
low to mid (the range containing 1),
mid to high (the range containing unknown elements)
and high to N (the range containing 2).
* Traverse the array from start to end and mid is less than high. (Loop counter is i)
* If the element is 0 then swap the element with the element at index low and update low = low + 1 and mid = mid + 1
* If the element is 1 then update mid = mid + 1
* If the element is 2 then swap the element with the element at index high and update high = high – 1 and update i = i – 1.
As the swapped element is not processed
* Print the array.
// C++ program to sort an array with 0, 1 and 2 in a single pass
#include (bits/stdc++.h>
using namespace std;
// Function to sort the input array, the array is assumed to have values in {0, 1, 2}
void sort012(int a[], int arr_size){
int lo = 0;
int hi = arr_size - 1;
int mid = 0;
// Iterate till all the elements are sorted
while (mid (= hi) {
switch (a[mid]) {
// If the element is 0
case 0: swap(a[lo++], a[mid++]);
break;
// If the element is 1 .
case 1: mid++;
break;
// If the element is 2
case 2: swap(a[mid], a[hi--]);
break;
}
}
}
// Function to print array
arr[]void printArray(
int arr[], int arr_size){
// Iterate and print every element
for (int i = 0; i ( arr_size; i++)
cout (( arr[i] (( " ";
}
// Driver Code
int main(){
int arr[] = { 0, 1, 1, 0, 1, 2, 1, 2, 0, 0, 0, 1 };
int n = sizeof(arr) / sizeof(arr[0]);
sort012(arr, n);
cout (( "array after segregation ";
printArray(arr, n);
return 0;}
Complexity Analysis:
Time Complexity: O(n).Only one traversal of the array is needed.
Space Complexity: O(1).No extra space is required.
Another approach-
Count the number of 0s, 1s and 2s in the given array. Then store all the 0s in the beginning followed by all the 1s then all the 2s.
Algorithm:
* Keep three counter c0 to count 0s, c1 to count 1s and c2 to count 2s
* Traverse through the array and increase the count of c0 if the element is 0,increase the count of c1 if the element is 1 and increase the count of c2 if the element is 2
* Now again traverse the array and replace first c0 elements with 0, next c1 elements with 1 and next c2 elements with 2.
Implementation:
// C++ implementation of the approach
#include (bits/stdc++.h>
using namespace std;
// Utility function to print the contents of an array
void printArr(int arr[], int n){
for (int i = 0; i ( n; i++)
cout (( arr[i] (( " ";
}
// Function to sort the array of 0s, 1s and 2s
void sortArr(int arr[], int n){
int i, cnt0 = 0, cnt1 = 0, cnt2 = 0;
// Count the number of 0s, 1s and 2s in the array
for (i = 0; i ( n; i++) {
switch (arr[i]) {
case 0: cnt0++;
break;
case 1: cnt1++;
break;
case 2: cnt2++;
break;
}
}
// Update the array
i = 0;
// Store all the 0s in the beginning
while (cnt0 > 0) {
arr[i++] = 0;
cnt0--;
}
// Then all the 1s
while (cnt1 > 0) {
arr[i++] = 1;
cnt1--;
}
// Finally all the 2s
while (cnt2 > 0) {
arr[i++] = 2;
cnt2--;
}
// Print the sorted array
printArr(arr, n);
}
// Driver code
int main(){
int arr[] = { 0, 1, 1, 0, 1, 2, 1, 2, 0, 0, 0, 1 };
int n = sizeof(arr) / sizeof(int);
sortArr(arr, n);
return 0;
}
Move all negative numbers to beginning and positive to end with constant extra space
Approach: We can solve this problem using the partision approach used in quick sort.
The process mimics quicksort’s partitioning:
Iterate Through the Array:
Loop through all elements of the array, checking if they satisfy <= 0.
Partitioning Based on Condition:
When an element satisfies <= 0:
Move it to the “left group” by swapping it with the element at position j (pointer tracking the boundary between the groups).
Increment j to expand the boundary of the left group.
Result After Partition:
At the end of the loop:
All elements before index j are non-positive (<= 0).
All elements after index j are positive (> 0).
public static void main(String[] args) {
int[] input = {-1, 2, -3, 1, 1};
move(input);
for (int j : input) {
System.out.print(j + " ");
}
}
private static void move(int[] input) {
int j = 0;
int temp;
for (int i = 0; i < input.length; i++) {
if (input[i] <= 0) {
if (i != j) {
temp = input[i];
input[i] = input[j];
input[j] = temp;
}
j++;
}
}
}
Given two arrays a[]and b[]of size nand m respectively. The task is to find union between these two arrays. Union of the two arrays can be defined as the set containing distinct elements from both the arrays. If there are repetitions, then only one occurrence of element should be printed in the union. Example 1: Input: 5 3 1 2 3 4 5 1 2 3 Output: 5 Explanation: 1, 2, 3, 4 and 5 are the elements which comes in the union set of both arrays. So count is 5. Example 2: Input: 6 2 85 25 1 32 54 6 85 2 Output: 7 Explanation: 85, 25, 1, 32, 54, 6, and 2 are the elements which comes in the union set of both arrays. So count is 7.
Your Task:
Complete doUnion funciton that takes a, n, b, m as parameters and returns the count of union elements of thetwo arrays. The printing is done by the driver code.
Constraints:1 ≤ n, m≤ 1050 ≤ a[i], b[i] 5
Expected Time Complexity : O((n+m)log(n+m))
Expected Auxilliary Space : O(n+m)
int doUnion(int a[], int n, int b[], int m) {
set s;
s.insert(a, a+n);
s.insert(b, b+m);
return s.size();
}Largest Sum Contiguous Subarray
Using kadane's algorithm
// C++ program to print largest contiguous array sum
#include(iostream>
#include(climits>
using namespace std;
int maxSubArraySum(int a[], int size){
int max_so_far = INT_MIN, max_ending_here = 0;
for (int i = 0; i ( size; i++){
max_ending_here = max_ending_here + a[i];
if (max_so_far ( max_ending_here)
max_so_far = max_ending_here;
if (max_ending_here ( 0)
max_ending_here = 0;
}
return max_so_far;
}
/*Driver program to test maxSubArraySum*/
int main(){
int a[] = {-2, -3, 4, -1, -2, 1, 5, -3};
int n = sizeof(a)/sizeof(a[0]);
int max_sum = maxSubArraySum(a, n);
cout (( "Maximum contiguous sum is " (( max_sum;
return 0;
}
Another approach-
#include(iostream>
using namespace std;
int maxSubArraySum(int a[], int size){
int max_so_far = a[0];
int curr_max = a[0];
for (int i = 1; i ( size; i++){
curr_max = max(a[i], curr_max+a[i]);
max_so_far = max(max_so_far, curr_max);
}
return max_so_far;
}
/* Driver program to test maxSubArraySum */
int main(){
int a[] = {-2, -3, 4, -1, -2, 1, 5, -3};
int n = sizeof(a)/sizeof(a[0]);
int max_sum = maxSubArraySum(a, n);
cout (( "Maximum contiguous sum is " (( max_sum;
return 0;
}
Given an array arr[], the task is to find the elements of a contiguous subarray of numbers which has the largest sum.
Examples:
Input: arr = [-2, -3, 4, -1, -2, 1, 5, -3]
Output: [4, -1, -2, 1, 5]
Explanation:In the above input the maximum contiguous subarray sum is 7 and the elements of the subarray are [4, -1, -2, 1, 5]
Input: arr = [-2, -5, 6, -2, -3, 1, 5, -6]
Output: [6, -2, -3, 1, 5]
Explanation:In the above input the maximum contiguous subarray sum is 7 and the elementsof the subarray are [6, -2, -3, 1, 5]
Naive Approach: The naive approach is to generate all the possible subarray and print that subarray which has maximum sum.
Time complexity: O(N2)
Auxiliary Space: O(1)
Efficient Approach: The idea is to use the Kadane’s Algorithm to find the maximum subarray sum and store the starting and ending index of the subarray having maximum sum and print the subarray from starting index to ending index.
Below are the steps:
Initialize 3 variables endIndex to 0, currMax and globalMax to first value of the input array.
For each element in the array starting from index(say i) 1, update currMax to max(nums[i], nums[i] + currMax) and globalMax and endIndex to i only if currMax > globalMax.
To find the start index, iterate from endIndex in the left direction and keep decrementing the value of globalMax until it becomes 0. The point at which it becomes 0 is the start index.
Now print the subarray between [start, end].
Below is the implementation of the above approach:
// C++ program for the above approach
#include (bits/stdc++.h>
using namespace std;
// Function to print the elements of Subarray with maximum sum
void SubarrayWithMaxSum(vector(int>& nums){
// Initialize currMax and globalMax with first value of nums
int endIndex;
int currMax = nums[0];
int globalMax = nums[0];
// Iterate for all the elements of the array
for (int i = 1; i < nums.size(); ++i) {
// Update currMax
currMax = max(nums[i],nums[i] + currMax);
// Check if currMax is greater than
globalMax
if (currMax > globalMax) {
globalMax = currMax;
endIndex = i;
}
}
int startIndex = endIndex;
// Traverse in left direction to find start Index of subarray
while (startIndex >= 0) {
globalMax -= nums[startIndex];
if (globalMax == 0) break;
// Decrement the start index
startIndex--;
}
// Printing the elements of subarray with max sum
for (int i = startIndex;i (= endIndex; ++i) {
cout << nums[i] << " ";
}
}
// Driver Codeint main(){
// Given array arr[]
vector(int> arr= { -2, -5, 6, -2, -3, 1, 5, -6 };
// Function callSubarrayWithMaxSum(arr);
return 0;
}
Kadane’s algorithm
Initialize:
max_so_far = INT_MIN
max_ending_here = 0
Loop for each element of the array
(a) max_ending_here = max_ending_here + a[i]
(b) if(max_so_far < max_ending_here) max_so_far = max_ending_here
(c) if(max_ending_here < 0) max_ending_here = 0
return max_so_far
Explanation:The simple idea of Kadane’s algorithm is to look for all positive contiguous segments of the array (max_ending_here is used for this). And keep track of maximum sum contiguous segment among all positive segments (max_so_far is used for this). Each time we get a positive-sum compare it with max_so_far and update max_so_far if it is greater than max_so_far
Find peak element in a sorted array
Given an array of integers. Find a peak element in it. An array element is a peak if it is NOT smaller than its neighbours. For corner elements, we need to consider only one neighbour.
Example:
Input: array[]= {5, 10, 20, 15}
Output: 20
The element 20 has neighbours 10 and 15,
both of them are less than 20.
Input: array[] = {10, 20, 15, 2, 23, 90, 67}
Output: 20 or 90
The element 20 has neighbours 10 and 15,
both of them are less than 20, similarly 90 has neighbours 23 and 67.
Following corner cases give better idea about the problem.
If input array is sorted in strictly increasing order, the last element is always a peak element. For example, 50 is peak element in {10, 20, 30, 40, 50}.
If the input array is sorted in strictly decreasing order, the first element is always a peak element. 100 is the peak element in {100, 80, 60, 50, 20}.
If all elements of input array are same, every element is a peak element.
It is clear from the above examples that there is always a peak element in the input array.
Naive Approach: The array can be traversed and the element whose neighbours are less than that element can be returned.
Algorithm:
If in the array, the first element is greater than the second or the last element is greater than the second last, print the respective element and terminate the program.
Else traverse the array from the second index to the second last index
If for an element array[i], it is greater than both its neighbours, i.e., array[i] > array[i-1] and array[i] > array[i+1], then print that element and terminate.
// A C++ program to find a peak element #include (bits/stdc++.h> using namespace std;
// Find the peak element in the array
int findPeak(int arr[], int n)
{
// first or last element is peak element
if (n == 1)
return 0;
if (arr[0] >= arr[1])
return 0;
if (arr[n - 1] >= arr[n - 2])
return n - 1;
// check for every other element
for (int i = 1; i ( n - 1; i++) {
// check if the neighbors are smaller if (arr[i] >= arr[i - 1] && arr[i] >= arr[i + 1]) return i; } }
// Driver Code
int main()
{
int arr[] = { 1, 3, 20, 4, 1, 0 };
int n = sizeof(arr) / sizeof(arr[0]);
cout (( "Index of a peak point is "
(( findPeak(arr, n);
return 0;
}
Output:
Index of a peak point is 2
Complexity Analysis:
Time complexity: O(n).
One traversal is needed so the time complexity is O(n)
Space Complexity: O(1).
No extra space is needed, so space complexity is constant
Efficient Approach: Divide and Conquer can be used to find a peak in O(Logn) time. The idea is based on the technique of Binary Search to check if the middle element is the peak element or not. If the middle element is not the peak element, then check if the element on the right side is greater than the middle element then there is always a peak element on the right side. If the element on the left side is greater than the middle element then there is always a peak element on the left side. Form a recursion and the peak element can be found in log n time.
Algorithm:
Create two variables, l and r, initialize l = 0 and r = n-1
Iterate the steps below till l <= r, lowerbound is less than the upperbound
Check if the mid value or index mid = (l+r)/2, is the peak element or not, if yes then print the element and terminate.
Else if the element on the left side of the middle element is greater then check for peak element on the left side, i.e. update r = mid – 1
Else if the element on the right side of the middle element is greater then check for peak element on the right side, i.e. update l = mid + 1
// A C++ program to find a peak element // using divide and conquer #include (bits/stdc++.h> using namespace std;
// A binary search based function
// that returns index of a peak element
int findPeakUtil(int arr[], int low,
int high, int n)
{
// Find index of middle element
// (low + high)/2
int mid = low + (high - low) / 2;
// Compare middle element with its // neighbours (if neighbours exist) if ((mid == 0 || arr[mid - 1] (= arr[mid]) && (mid == n - 1 || arr[mid + 1] (= arr[mid])) return mid;
// If middle element is not peak and its // left neighbour is greater than it, // then left half must have a peak element else if (mid > 0 && arr[mid - 1] > arr[mid]) return findPeakUtil(arr, low, (mid - 1), n);
// If middle element is not peak and its // right neighbour is greater than it, // then right half must have a peak element else return findPeakUtil( arr, (mid + 1), high, n); }
// A wrapper over recursive function findPeakUtil()
int findPeak(int arr[], int n)
{
return findPeakUtil(arr, 0, n - 1, n);
}
// Driver Code
int main()
{
int arr[] = { 1, 3, 20, 4, 1, 0 };
int n = sizeof(arr) / sizeof(arr[0]);
cout (( "Index of a peak point is "
(( findPeak(arr, n);
return 0;
}
Output:
Index of a peak point is 2
Complexity Analysis:
Time Complexity: O(Logn).
Where n is the number of elements in the input array. In each step our search becomes half. So it can be compared to Binary search, So the time complexity is O(log n)
Space complexity: O(1).
No extra space is required, so the space complexity is constant.
Minimize the maximum difference between the heights
Given heights of n towers and a value k. We need to either increase or decrease the height of every tower by k (only once) where k > 0. The task is to minimize the difference between the heights of the longest and the shortest tower after modifications and output this difference.
Examples:
Input : arr[] = {1, 15, 10}, k = 6
Output : Maximum difference is 5.
Explanation : We change 1 to 7, 15 to
9 and 10 to 4. Maximum difference is 5
(between 4 and 9). We can't get a lower
difference.
Input : arr[] = {1, 5, 15, 10}
k = 3
Output : Maximum difference is 8
arr[] = {4, 8, 12, 7}
Input : arr[] = {4, 6}
k = 10
Output : Maximum difference is 2
arr[] = {14, 16} OR {-6, -4}
Input : arr[] = {6, 10}
k = 3
Output : Maximum difference is 2
arr[] = {9, 7}
Input : arr[] = {1, 10, 14, 14, 14, 15}
k = 6
Output: Maximum difference is 5
arr[] = {7, 4, 8, 8, 8, 9}
Input : arr[] = {1, 2, 3}
k = 2
Output: Maximum difference is 2
arr[] = {3, 4, 5}
First, we try to sort the array and make each height of the tower maximum. We do this by decreasing the height of all the towers towards the right by k and increasing all the height of the towers towards the left (by k). It is also possible that the tower you are trying to increase the height doesn’t have the maximum height. Therefore we only need to check whether it has the maximum height or not by comparing it with the last element towards the right side which is a[n]-k. Since the array is sorted if the tower’s height is greater than the a[n]-k then it’s the tallest tower available. Similar reasoning can also be applied for finding the shortest tower.
Note:- We need not consider where a[i]
using namespace std;
// User function Template
int getMinDiff(int arr[], int n, int k)
{
sort(arr, arr + n);
int ans = arr[n - 1] - arr[0]; // Maximum possible height difference
int tempmin, tempmax;
tempmin = arr[0];
tempmax = arr[n - 1];
for (int i = 1; i ( n; i++) {
tempmin= min(arr[0] + k,arr[i] - k); // Minimum element when we add k to whole array
tempmax = max(arr[i - 1] + k, arr[n - 1] - k); // Maximum element when we subtract k from whole array ans = min(ans, tempmax - tempmin); } return ans; }
// Driver Code Starts
int main()
{
int k = 6, n = 6;
int arr[n] = { 7, 4, 8, 8, 8, 9 };
int ans = getMinDiff(arr, n, k);
cout (( ans;
}
