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

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

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

math

• Just calculate sum of first n numbers

• calculate the sum of elements of array

• return their abs(difference)

Union of two sorted arrays

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

two ptr

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

Same as union of arrays

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

Leaders in an Array

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

• 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

Print the matrix in spiral manner

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

$$\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

        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 nth row

  • then

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

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

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