Arrays | Must-known DSA Array Techniques

Webinar by Scalar and Naman Bhalla
What are Arrays?
*Linear Data Structure
*A way to store data of the same time
*Allows to get a value at any position in O(1) time

How to implement Arrays in Java ?

in Java:
int[] arrayName =new int[size]

in javascript/python:
we can store different data types because it point to the object referencing
array implementation in python and js

How does Array store data?
Array store data in different address of the RAM
int arr[4]- each int is 4 byte, 4*4 elements
16 byte is allocated when we run the program.

=

Finding Element in Arrays-
if the array is 0 indexed then , if we have to find the 3rd element, then we look for 3-1 i.e. n-1 multiple from the start position/index

13+2*4= 13+8=21 so element will be stored at 21th address

*Dynamic Arrays- *
in case of JS and python
in dynamic array no need to tell the size of the array, you can keep adding the elements infinitely, but it has to be restricted by RAM size or till the time out of memory size

in C++- Vectors
in Java- ArrayList
in Python-
in js - {}(list)

How Dynamic arrays work-
Dynamic array offer capacity and size.
capacity is arbitrary value defined by the programming language, size can be defined by user.

when array gets full initial capacity, the dynamic arrays provides extra capacity of 1.75* or 2*, depending on the programming language, this is all happening behind the scenes.

for N insertion :
the worst case is when added array will lead to creation of the new element and size increase.
time to insert+ capacity time or creating array + copy time
=N+[2N+ 2N/2+ 2N/4+.....]+[N+N/2+N/4+....]
=N+4N+2N=7N

sum of (1+1/2+1/4+1/8.....) will always be less than 2
for N insertion is nN/n = N
time complexity: O(1)

the Dynamic array has no loss, so feel free to use day to day and dynamic programming.
initialization and putting the value:
Vector array[]

array.push(11)

Follow Kritika Agarwal on Linkedin :
Kritika Agarwal Software Engineer II at Microsoft

create low level design application : Expense Sharing Application

prefix- something that has happened in an array till the particular index.

suffix- something that will happen in array after this index or something that has happened in the array till this index from the end.

prefix sum Array-
Image description

Psum Array = new arr[n]

** Psum[0]=
psum[3]=
**

sufixSum= [N]
suffixSum[N-1]= A[N-1]
for(i=n-2; i>=0; --i)
suffixSum[i]= SuffixSum[i+1] +A[i]

suffixMax= max(suffixMax[i+1], A[i])

I can only use for commutative property problem cases,XOR can be done, subtraction and division can not be done

Problem 1: Trapping Rainwater problem:
height of the building are following and width is 1.
Problem Link: https://leetcode.com/problems/trapping-rain-water/
heights[]= {9,3,2,1,3,1,2,8,3}

approach 1: Brute Force:
*Finding height after which is there are no resistance.
*finding areas where the support/building is on the both the sides which would be Tallest building on the both the sides
*height till water stored: min(A,B) , where A- tallest building on left, MaxLeft B- tallest on right, MaxRight

amount of water- Max(0, min(height till water stored- height[i])

for i=0 -> N-1:
maxLeft=0;
for j=0 to i-1
maxleft= Max(maxleft, height[j])

maxRight=0
for j= i+1 to N-1
MaxRight= Max(maxRight, height[1]);

heightTillWater= min(maxLeft, maxRight)

sum= max or 0;
sum= sum- height[i]

time complexity: O(N^2)

so we have to optimised

optimized Solution:

**> PrefixMax=

SuffixMax=**
for i=0 to N-1:
the edge cases will give you out of bound, the edge cases are basically 0, so we don not consider them

for [i=1 to N-2]:
maxLeft=Pmax[i-1]
maxRight=Smax[i+1]
heightTW= min(maxleft, maxright)
sum = Max(0, hieghtTW- height[i])
return sum
T.C. O(N) +O(N)+O(1)
SC O(N)

further optimization:

Book Recommendation :

Algorithms by CLAS
Algorithm Design by Kleinberg
Elements of Programming Interviews

Follow me on LinkedIn
twitter