Introduction to Arrays and Their Algorithms :

Arrays are fundamental data structures in computer science and

programming. They provide a way to store and organize multiple
elements of the same type in a contiguous block of memory. Arrays
offer efficient access to individual elements and enable various
algorithms to manipulate and process the data they hold.

An array is typically represented as a fixed-size collection of elements,

where each element can be accessed using an index or position within
the array. The index starts from zero for the first element and
increments by one for each subsequent element. This zero-based
indexing allows for direct and constant-time access to any element in
the array.
Arrays are widely used for various purposes, such as storing collections
of numbers, strings, or objects. They are employed in a wide range of
applications, including sorting and searching algorithms, dynamic
programming, graph algorithms, and many more.

Several important algorithms are designed specifically for arrays,

addressing common tasks like searching for an element, sorting the
array in a specific order, or performing various transformations on the
array’s elements. Here are some basic commonly used algorithms for
arrays:

1. The Kadane’s Algorithm

2. Dutch’s National Flag algorithm

3. Linear Search and Binary Search

4. Prefix and Suffix Sum

Now lets dive into the above algorithms step by step

Kadane’s Algorithm :

Kadane’s Algorithm is a dynamic programming algorithm used to find

the maximum subarray sum in an array of numbers. It efficiently
solves the maximum subarray problem and has a time complexity of
O(n), where n is the size of the array.
Problem statement:

Given an array of N integers a1,a2,a3,….., aN . Find the maximum

subarray(non-empty) sum of the given array.

For example: Array A[]= [-1, 2, -2, 5, 7, -3, 1]

Maximum subarray sum -> 12 Subarray(0-Based indexed) from index

1 to 4 -> [2, -2, 5, 7] and subarray(0-Based indexed) from index 3 to 4 -
> [5, 7] have sum 12.

Kadane’s Algorithm The idea of Kadane’s algorithm is to maintain a

maximum subarray sum ending at every index ‘i’ of the given array and
update the maximum sum obtained by comparing it with the
maximum sum of the subarray ending at every index ‘i’. At any given
index ‘i’ of the array, we can either: ●Append the element at index ‘i’ to
the maximum sum subarray(so just add the element at index ‘i’ to the
maximum you’ve found so far). ●Start a new subarray starting from
index ‘i’. Appending an element at index ‘i’ to the maximum sum
subarray obtained so far is beneficial if the sum till index ‘i-1’ is non-
negative, otherwise it is better to start a new subarray starting from
index ‘i’ and update the maximum sum obtained accordingly.
Pseudo- code :

function Kadane(arr, N) //Initializing curSum to 0 and maxSum to min value,

denoting an empty subarray
curSum = 0
maxSum = INT_MIN
for idx = 0 to N-1
curSum = curSum + arr[idx]
//Taking the max of maxSum and the curSum of the subarray
maxSum = max(maxSum,curSum)
//Checking if the curSum becomes negative
if curSum < 0
curSum = 0
return maxSum

Time complexity: O(N), where N is the number of elementsin the array, as we

traverse the array once to get the maximum subarray sum.
Space complexity: O(1), as no extra space is required.

Implementation:

Flip bits:

Problem Statement: You are given an array of integers ARR[] and size
of N consisting of zeros and one’s .You have to select a subset and flip
the bits of that subsets . You have to return the count of maximum
one’s that you can obtain by flipping choosing subarray’s at most once.
A flip operation is one in which you turn 1 into 0 and 0 into 1.

Constraints:

1 ≤ T = 100, 1 < N ≤ 10⁴, 0 ≤ ARR[i] ≤ 1.

Walk through: If you are given an array of {1,1,0,0,1,1} .Then you will
have to return the count of the maximum one’s you can obtain by
flipping any choosing sub-array at most once . so here you will clearly
sub-array from the index of 2 to 3 .And flip its bits , So the final array
comes out to be { 1,1,1,1,1,1} which contains 5 one’s so you will return 5.

Code:

#include <iostream>;
#include <bits/stdc++.h>;
using namespace std;
int flipBits(int* arr, int n)
{
// initializing a variable l at zero
int l =0;
// iterating through the array
for(int i = 0 ; i < n; i++){
// if array at any index is one
// changing the value at that index to be -1
if(arr[i] == 1){
arr[i] = -1;
// upon incrementing it becomes 0
// flipping values that are -1 to 0
l++;
}
// if the values are 0 then flip them to 1
else{
arr[i] = 1;
}
}
// implemetation of the kandanes algorithm
int sum = 0;
int maxsum = 0;
for(int i = 0; i < n; i ++){
sum = sum + arr[i];
maxsum = max(maxsum , sum );
if(sum < 0){
sum = 0;
}
}
// returning the count for the maximum of 1 in the array
return l + maxsum;
}
This is a basic idea of how the Kadane's Algorithm works.

Dutch’s National Flag Algorithm:

The Dutch National Flag algorithm, also known as the 3-way

partitioning algorithm , is a sorting algorithm proposed by Dutch
computer scientist Edsger Dijkstra. It is named after the Dutch
national flag because it was originally designed to solve a problem
related to sorting arrays with three distinct values. The algorithm is
used to partition an array of elements with three possible values
(commonly represented as colours) into three regions: elements that
are smaller than a given value, elements that are equal to the given
value, and elements that are larger than the given value. The goal is to
rearrange the elements in the array in linear time complexity.

The Dutch National Flag algorithm or three-way partitioning algorithm

allows sorting the array consisting of 0s, 1s, and 2s in a single traversal
only and in constant space. Steps: ●Maintain three indices low = 0,
mid = 0, and high = N-1, where N is the number of elements in the
array.

1. The range from 0 to low denotes the range containing 0s.

2. The range from low to mid denotes the range containing 1s.

3. The range from mid to high denotes the range containing any of 0s,
1s, or 2s.
4. The range from high to N-1 denotes the range containing 2s. ●The
mid pointer denotes the current element, traverses the array while
mid<=high i.e we have exhausted the search space for the range
which can contain any of 0s, 1s, or 2s. 1.If A[mid] == 0, swap
A[mid] and A[low] and increment low and mid pointers by 1. 2.If
A[mid] == 1, increment the mid pointer by 1. 3.If A[mid] == 2,
swap A[high] and A[mid] and increment mid by 1 and decrement
high by 1. The resulting array will be a sorted array containing 0s,
1s, and 2s.

Pseudo-code:

function DNF(arr, N) //Initializing low, mid and high pointers

low = 0
mid = 0
high = N-1
while mid <= high
/* Check if arr[mid] == 0, swap arr[low] and arr[mid], increment mid and low
pointers */
if arr[mid] == 0
swap(arr[mid],arr[low])
low += 1
mid += 1
//Check if arr[mid] == 1, increment mid pointer
else if arr[mid] == 1
mid += 1
/* Check if arr[mid] == 2, swap arr[mid] and arr[high], decrement high
pointer and increment low pointer */
else if arr[mid] == 2
swap(arr[mid],arr[high])
high -= 1

Time complexity: O(N), where N is the number of elementsin the array, as we

sort the array in a single traversal only.
Space complexity: O(1), as no extra space is required.

Implementation:
Sort 0 1 2:

Problem Statement: You are given an integer arr/list(ARR) of size “N” ,

It only contains 0s , 1s and 2s. Write a Solution to sort this array /List .

Constraints:

1≤ T≤ 100 , 1≤ N ≤ ( 5 X 10⁵) , 0 ≤ ARR[i] ≤ 2

Code:

#include <bits/stdc++.h>
# include <iostream>
using namespace std;
void sort012(int *arr, int n)
{
//using the dutch national flag algorithm
int low = 0;
int mid = 0;
int high = n-1;

while(mid <= high){

if(arr[mid] == 0 ){
swap(arr[mid] , arr[low]);
low +=1;
mid +=1;
}
else if(arr[mid] == 1){
mid+=1 ;
}
else if(arr[mid] ==2){
swap(arr[mid] , arr[high]);
high -= 1;
}

}
}
Searching(Linear and Binary Search):

Searching means to find out whether a particular element is present in

the given array/list. For instance, when you visit a simple google page
and type anything that you want to know/ask about, basically you are
searching that topic in Google's huge database for which google is
using some technique in order to provide the desired result to you.
There are basically two types of searching techniques:

●Linear search

●Binary search

Linear Search :It is a simple sequential search over all the elements of
the array, and each element is checked for a match, if a match is found
return the element otherwise the search continues until we reach the
end of the array.

Pseudo-Code:

/* array from leftidx(0) to rightidx(arr.length-1) is considered */

function linearSearch(arr, leftidx , rightidx , target)

// Search for the target from the beginning of arr

for idx = 0 to arr.length-1

if arr[idx] == target
return idx
// target is not found
return -1
Time complexity: O(N), as we traverse the array only once to check for a
match for the target element.
Space complexity: O(1), as no extra space is required.

Binary Search: Search in a sorted array by repeatedly dividing the array

into two halves and searching in one of the halves. Suppose you want
to find a particular element in the sorted array, then following this
technique, you have to traverse all the array elements for searching one
element but guess if you only have to search at most half of the array
indices for performing the same operation. This can be achieved
through binary search. Note (Binary search works on a sorted array
because it utilizes the property of a sorted sequence to efficiently locate
a specific target value. The algorithm repeatedly divides the search
space in half, reducing the search range by half with each comparison)

Pseudo-code:

/* array of size N from 0 to N-1 is considered */

function binarySearch(arr, N, target)

// Initializing lo and hi pointers
lo = 0
hi = N-1
//
Searching for the target element until lo<=hi //

while lo <= hi
Finding the mid of search space from lo to hi

mid = lo + (hi-lo)/2
//
If the target element is present at mid
 if arr[mid] == target
return mid
/* If the target element is less than arr[mid], then if the target is
present, it must be in the left half. */

if target < arr[mid]

hi = mid-1
// Otherwise if the target is present, it must be in the right half

else lo = mid+1

// If the target is not found return -1

return -1

Time complexity: O(logN), where N is the number ofelements in the array,

given the array is sorted.
Since we search for the target element is one of the halves every time,
reducing our search space
to half of the current search space.

Space complexity: O(1), as no extra space is required.

Implementation:

Search in Rotated Sorted Array:

Problem Statement : Aahad and Harsit always have fun in solving

problems .Harsit took a sorted array consisting of distinct integers and
rotated it clockwise by an unknown amount. For example , he took a
sorted array =[ 1,2,3,4,5] and if he rotates it by 2 , then the array
becomes: [4,5,1,2,3] . After rotating a sorted array , Aahad needs to
answer Q queries asked by Harsit , each of them is described by one
integer Q[i] . which Harsit wanted him to search in the array . For each
query , if he found it .He had to shout the index of the number ,
otherwise he had to shout -1. For each query you have to complete the
given ‘key’ denotes Q[i]. if the key exists in the array , return the index
of the ‘key’ otherwise return -1.

Constraints:

1≤ N ≤ 10⁶ , -10⁹ ≤ A[i] ≤ 10⁹ , 1 ≤ Q ≤ 10⁵ , -10⁹ ≤ Q[i] ≤ 10⁹

Code:

// linear Search solution

// time complexity O(N) , Space complexity O(1)

int search(int* arr, int n, int key)

{
// Iterate through the array
for (int i = 0; i < n; ++i)
{
// key is found
if (arr[i] == key)
{
return i;
}
}
// key not found
return -1;
}

// optimal solution
// Binary Search.
// Time complexity O(logN) , Space complexity O(1)
int search(int* arr, int n, int key)
{
// Initialize start and end
int st = 0, end = n - 1;

// Performing binary search

while (st <= end)
{
// Get the middle element
 int mid = st + (end - st) / 2;
// The middle element is the one we are searching for
if (arr[mid] == key)
{
return mid;
}
else if (arr[mid] >= arr[st])
{
// Element lies towards left of mid
if (arr[st] <= key && key <= arr[mid])
{
end = mid - 1;
}
// Element lies towards right of mid
else
{
st = mid + 1;
}
}

else
{
// Element lies towards right of mid
if (arr[end] >= key && key >= arr[mid])
{
st = mid + 1;
}

// Element lies towards left of mid

else
{
end = mid - 1;
}
}
}
// Element not found
return -1;
}

These are just the basic implementation of linear and Binary search.

Prefix and Suffix Sum:

Prefix Sum:

Given an array ‘A’ of size N, its prefix sum array is an array of the same
size N. Such that the its element of the prefix sum array “Prefix” is the
sum of all elements of the given array till its ith index from the
beginning, i.e Prefix[i] = A[0] + A[1] + A[2] + ……. + A[i].

For Example: Given A[] = [3 , 4, -1, 2, 5], the prefix sum array P[] is
given as: P[0] = 3 , P[1] = 7 , p[2] = 6 , P[3] = 8 , P[4] = 13 .. i.e P[] = [ 3
, 7, 6 , 8, 13]

Suffix Sum :

Given an array ‘A’ of size N. its Suffix sum array is an array of the same
size N such that the ith element of the suffix sum array ‘Suffix’ is the
sum of the given array till ith index from the end i.e Suffix[i] = A[i] +
A[i+1] + A[i +2] + …+ A[N-1] (0- Based indexing )

For example: Given A[] = [ 3, 4 ,-1, 2,5] , the suffix sum array S[] is
given as S[0] = 13 , S[1] = 10 , S[2] = 6 , S[3] = 7 , S[4] = 5 …. i.e S[] =
[13 , 10 , 6 , 7 , 5]

Implementation:

Product of Array Except Self:

Problem: You have been given an integer array/list (ARR) of size N.
You have to return an array/ List PRODUCT such that PRODUCT[i] is
equal to the product of all elements of the array ARR except ARR[i]

Constraints:

1 ≤ T ≤ 100 , 0 ≤ N ≤ 10⁵ , 0 ≤ ARR[i] ≤ 10⁵

Code:

/*
Time Complexity : O(N)
Space complexity : O(N)

where N is the size of the input array

*/

/*

x = a * b * c * d
log(x) = log(a * b * c * d)
log(x) = log(a) + log(b) + log(c) + log(d)
x = antilog(log(a) + log(b) + log(c) + log(d))
Traverse the array and find the sum of log of all the elements.
Then again traverse through the array and find the product using this
formula.
antilog((log(a[0]) + log(a[1]) +...... + log(a[n-1])) - log(a[i]))
This equals to product of all the elements except a[i], i.e antilog(sum-
log(a[i])).
*/

int multiply(int a, int b)

{
int mod = 1e9 + 7;
long long ret = a % mod;
ret *= (b % mod);
ret = ret % mod;
return ret;
}
//Calculate the suffix Array
int *getPrefixArray(int *arr, int n)
{
int productTillNow = 1L;

int *prefixArray = new int[n];

for (int i = 0; i < n; i++)

{
prefixArray[i] = productTillNow;
productTillNow = multiply(productTillNow, arr[i]);
}

return prefixArray;
}

//Calculate the prefix Array

int *getSuffixArray(int *arr, int n)
{
int productTillNow = 1L;

int *suffixArray = new int[n];

for (int i = n - 1; i >= 0; i--)

{
suffixArray[i] = productTillNow;
productTillNow = multiply(productTillNow, arr[i]);
}

return suffixArray;
}

int *getProductArrayExceptSelf(int *arr, int n)

{
//Array storing the product of all elements before the current element
int *prefixArray = getPrefixArray(arr, n);

//Array storing the product of all elements after the current element
int *suffixArray = getSuffixArray(arr, n);

//Array to store the answer

int *answerArray = new int[n];

for (int i = 0; i < n; i++)

{
//Answer is the product of all elements before and after the current
element.
answerArray[i] = multiply(suffixArray[i], prefixArray[i]);
}

delete prefixArray;
delete suffixArray;
 //Return the answer
return answerArray;
}