Array is one of the most important topic in DSA as it is used in every other topic so it is the basic necessity for solving DSA problems

Introduction

What is DSA ?

Nothing but a contagious way to store data of similar datatype ( eg: int, string , char etc )

Ways to declare an Array ?

1. C-style Array (fixed-size on stack)

int arr[5];            // uninitialized
int arr2[5] = {1, 2};  // {1, 2, 0, 0, 0}
int arr3[] = {1, 2, 3}; // size inferred: 3

2. std::array (C++11+, fixed size, safer than C-array)

#include <array>

std::array<int, 5> arr;                 // default-initialized
std::array<int, 5> arr2 = {1, 2, 3};    // {1, 2, 3, 0, 0}

• Size is fixed at compile time

• Has .size(), .at(), .begin(), .end(), etc.

3. std::vector (dynamic size, most common in CP)

#include <vector>

std::vector<int> v;                         // empty
std::vector<int> v2(5);                     // {0, 0, 0, 0, 0}
std::vector<int> v3(5, 7);                  // {7, 7, 7, 7, 7}
std::vector<int> v4 = {1, 2, 3, 4};         // list initialization

• Size can grow/shrink

• Preferred in competitive programming / DSA

• Has .push_back(), .resize(), etc.

4. Dynamic Array via new/delete (Heap allocation)

int* arr = new int[5];       // uninitialized
delete[] arr;                // don't forget to delete

Problems

Basic Problems are

• Linear Search

• Largest Element

• Second Largest Element

• Maximum Consecutive Ones

• Left Rotate Array by One

• Left Rotate Array by k Places

» Other Problems are

Move Zeros to End code

Two Pointer approach

• Keep both pointer at start s = 0 , m = 0

• m scans all the elements

• s stays at index where next non-zero element should go

• and if m ptr is at some non-zero element then swap the element with s ptr

• and move both ptr by one

• if m ptr is at 0 then just move it further

• It will make sure that your

  • before s all the elements are non zero and s will be swiping out your zeros to end

  • and as your m ptr is not moving any zero, it is moving only non zero to ptr s so all zero will eventually be by handled s and will be [ushed to end

Remove duplicates from sorted array code

Two Pointer

Define two ptrs curr = 0 , next = 0

• curr stays at a index before which no duplicates exist

• next Scans the array and finds next distinct element to be placed after curr

How it works

• next ptr picks an element and compares it with element at curr i

  • if they are same next moves ahead by one step

  • if they are different moves curr by one step and and then swaps element at curr with element at next and moves next by one

• Return curr + 1 as length of subarray from 0 to curr

Find missing number code

math

• Just calculate sum of first n numbers

• calculate the sum of elements of array

• return their abs(difference)

Union of two sorted arrays code

two pointer

The union of two arrays is an array where all values are distinct and are present in either the first array, the second array, or both.

» Brute Force : using set

» Optimal : using two ptrs

How it works

» Will use power of arrays being sorted

• ptr1 = 0 for first array

• ptr2 = 0 for second array

• now run a loop till either of ptrs hit size of respective arrays

• and also make sure you skip all the duplicates in one array itself by internal while loops

• and keep inserting unique and distinct elements in ans array

• and if any array has elements that are not pushed in ans array just push it in ans array

• return ans

Intersection of two sorted arrays code

two ptr

The intersection of two arrays is an array where all values are present in both arrays.

Same as union of arrays but here duplicated elements are allowed as they have same number of copies in each array

• just push element to ans array if both array has it

Leaders in an Array code

Just as question says

A leader in an array is an element whose value is strictly greater than all elements to its right in the given array. The rightmost element is always a leader. The elements in the leader array must appear in the order they appear in the nums array.

Rearrange array elements by sign code

• define two arrays

  • one for positive elements

  • one for negative elements

• now place values from these two array to original array as requested in Problem statement

Other way would be

Create a new array<ans array> of same size and place elements in the ans array directly from given array using two pointers :

• one for positive elements at even indices

• one for negative elements at odd indices

Print the matrix in spiral manner code

Do just as question says

• will be solved using 4 ptrs

  • l = 0 , r = cols-1 , t=0 , b = rows- 1

• While moving pointers keep in mind about the bound or limit of how far a point can go

Pascal's Triangle

math

• The first row has one element with a value of 1.

• Each row has one more element in it than its previous row.

• The value of each element is equal to the sum of the elements directly above it when arranged in a triangle format.

For pascal triangle there are three type of questions

Print an Element at r rows and c cols of Pascal’s Triangle code

$$\text{required_ans} = \binom{r - 1}{c - 1}$$

» Brute : Find factorial multiple times

» Optimal : Use formula

$$(n/1 )* ((n-1)/2) * ...$$

example :

for n = 10 and r = 7

$$\binom{10}{7} = (10/1)((10 - 1)/2)((10 - 2)/3)$$

Print each element of rth row code

        for row 4 
        simulating

        1    1*3/1    (1 * 3 * 2)/( 1 * 2)     (1 * 3 * 2 *1)/(1 * 2 * 3)
        1    3         3                          1

• here first element is 1

• next element will be found by

  • if x is ith element

  • then (i+1)th element

  • and it is in nth row

  • then

$$\text{required_ans} = (1*(n-1)(n-2)...(n-i+1))/ (123...*i)$$

3. Print all n rows of pascal triangle from row 1 code

Just repeat 2nd problem solution for each row

or

just implement what it is

• The first row has one element with a value of 1.

• Each row has one more element in it than its previous row.

• The value of each element is equal to the sum of the elements directly above it when arranged in a triangle format

Rotate matrix by 90 degrees code

• Transpose → reverse each row

Two Sum code

• using map if order of element in ans has to be same

• can also use sort

Three Sum code

• Sorting is required

• Also as it is asking about unique combinations of elements to sum to 0 Think about using a set

• Here three pointers will be used

• one will be fixed at ith position (i = 0 → n-1)

• other two will apply two sum in remaining elements and will compare three sum by adding value of item at ith index

Four Sum code

Same as three sum

• Fix left most element and for rest elements apply three sum

Sort an array of 0's 1's and 2's : Dutch National Flag algorithm code

may have to use 3 pointers

• s = 0 : before which all zeroes will be present

• m = 0 : middle pointer responsible for placing 0s and 2s at their desired position

• e = n-1 : after which all twos will be present

Steps

for m → 0 to e

• arr[m] == 1 : m++ and continue

• arr[m] == 0 : swap element at m with elem at s and m++ and s++

• arr[m] == 2 : swap element at m with elem at e and m++ and e—

Kadane's Algorithm code

• assume maxSum is minimum possible value

• then iterate and keep adding every element to sum and compare it with maxSum

• if sum < 0 set sum = 0 and keep doing the same

Next Permutation code

The next permutation of an array of integers is the next lexicographically greater permutation of its integers.

More formally, if all the permutations of the array are sorted in lexicographical order, then the next permutation of that array is the permutation that follows it in the sorted order.

example :

for 1 3 2

next permutation is number strictly greater then this → 2 1 3

Steps

• Find the element for which arr[i] < arr[i+1] where i = n-2 → 0

• now pivot at that index i

• find the first element on right part of pivot which is greater then item at i

• swap it at i and with item found at previous step

• now reverse the right part of pivot excluding the ith element

Majority Element I : Moore's voting algorithm code

The majority element of an array is an element that appears more than n/2 times in the array. The array is guaranteed to have a majority element.

In this algorithm we keep track of

• ans : element which is desired

• cnt : freq of how many times ans repeated it self in the array

Steps

• for every value of i ; i = 0→ n-1

  • if cnt = 0 : we assume this is the ans

  • if cnt ≠ 0

    • if ans = arr[i] : cnt++

    • else : cnt—

now we will have a value in ans which is the possible ans as if element is appearing more than n/2 times means it will be the last one in ans variable

however it is possible that no item appear more that n/2 times ,

hence we count the freq of ans in complete array using for loop over complete array

• if it satisfies the condition of majority element: our ans

• else return -1

Majority Element-II code

all elements which appear more than n/3

Modification to moore voting element

• Only two possible ans will exist

Find the repeating and missing number code

A math problem always prefer it’s coding solution

solved using generation equations of sum of first n elements and sum of first n*n elements

Count Inversions code

Brute force: Generate all pairs by scanning all other elements for each selected elements and return count of such numbers

optimal : merge sort

Maximum product sub array in an Array code : todo

concept of prefix product and suffix product

• for even number of negative elements product of whole array will be positive

• for odd number of negative elements there will be a single negative element that will cause whole product to be negative.

  • hence ans would be either right part of that element

  • or left part of that element

• To handle case for zero just assign 1 to prefix product or suffix product if they get zero

• For each iteration compare and store the max of suffix or prefix product or if prev stored was already bigger then move on

• and return the final ans

Merge two sorted arrays without extra space code : todo

just make sure all them elements in one array are strictly smaller then all elements of other array

» Note : Array size of left array is given as total number of elements

Steps

• Consider two arrays left , right array

• point one ptr at end of left array

• point second ptr at start of right array

• traverse both such that elements in left always smaller then right

• push all the elements from right to left array