Lecture_Notes/imperfect_notes/pragy/intro week - Arrays and Maths.md

Intro Week - 2 - Arrays and Math

PRIVATE

• Explain that we're just giving a trailer for the first week. Will dive into much more detail later on. HLD tomorrow, LLD day after, special talk on Friday/Saturday.
• will cover DS/Algo, advanced problems, advanced topics like Segment Trees, lazy propagation, Fenwick Trees, Bitmask DP, Network Flow (Mincut-Maxflow)

PUBLIC

• We're assuming that you know what arrays are, basic loops, if else
• Anyone who doesn't understand arrays?
• Array is a collection of homogeneous data

C++ Vector vs Array

• how do arrays work?
  • allocate space of fixed size
• how are vectors different?
  • Vectors are dynamic. Arrays are not
• How are vectors allocated?
  • when space is full, how do we push_back?
    • double the space
    • Copy the current elements
    • Free previous array
  • what is the time complexity of inserting elements?
    • Time complexity - worst case - O(n)
    • Amortized - O(1)
  • Explain what "amortized" means
  • Actually have growth factor - 1.7, and not 2 to scale the array by
  • Overall, not a big overhead

Passing arrays by value / reference

int run() {
    int n;
    cin >> n;
    vector<int> v;
    for(int i = 0; i < n; i++) {
        int temp;
        cin >> temp;
        v.push_back(temp);
    }
    return find_middle(v);
}


int find_middle(vector<int> v) {
    return v[v.size() / 2];
}

C++

• Time complexity overall? O(n)
• For find_middle? O(n)
  • Note that here the passing is by value - the entire array is being copied
  • No changes will reflect if we make changes in the function

So, if you use pass by reference

int find_middle(vector<int> & v) {
    ...
}

• now it is being passed by reference
• Java has objects. Objects are passed. So, by reference. O(1), and mutable
• important because
  • passing by value can slow down the code
  • passing by reference can cause side effects

---

Absolute Values

A: 1 5 13 8 can have -ves Find i, j so that i != j and \Bigl | A[i] - A[j] \Bigr | + \Bigl | i - j \Bigr | is maximized

def abs(x):
    if x < 0: return -x
    else: return x

1. Ask clarifying questions
   • can we have -ve elements?
   • What happens when the array has size 1?
     • return -1
2. Think of the brute force appraoch
3. Optimize

Brute Force

O(n^2) - all combinations of i, j Get max

Optimized

Expand the expression if you don't see any patterns Expand the abs()

• enforce i > j

• Two cases:

  • A[i] > A[j]
    • = (A[i] + i) - (A[j] + j)
  • A[i] < A[j]
    • = (A[j] - j) - (A[i] - i)

• So, calculate (A[i] + i) as X and A([i] - i) as Y

• Find maxX, minX, maxY, minY

• return max((maxX-minX), (maxY-minY))

• How does this take care of i = j case?

  • i = j gives answer of 0
  • we know that since |i-j| > 0 for some (i, j), no matter what |A[i] - A[j]| is, our answer will at least be greater than 0

---

Trapping Rain

Buildings Rain from top. Find the area of the rain trapped.

Approach:

Look at a building. Amount of water that I can store is the min height of the tallest building on left and right

O(n^2)

• how can we calculate max and min efficiently?
  • Prefix and suffix max

prefix_max[0] = A[0];
for(int i = 1; i < N; i++)
    prefix_max[i] = max(prefix_max[i-1], A[i]);

suffix_max[N-1] = A[N-1];
for(int i = N-2; i >= 0; i--)
    suffix_max[i] = max(suffix_max[i-1], A[i]);

Now, for every element i, look at the prefix_max[i-1] and suffix_max[i+1] and take min-height

---

Max Gap

A = 2 5 13 8 7 6 unsorted array, duplicates possible if A as sorted, then find max(A[i+1] - A[i]) don't sort, use linear space

Make sure that everyone knows what sorting is

Approach: What is the max possible difference? max - min (min min min max max max) What is the min possible difference? (max-min) / (N-1) (min min+d min+2d .. max)

Now, create buckets with the size of gap

gap = (max - min) / (N-1)

Create buckets of size of gap

• can the two elements from the same bucket have the max-gap? No, because bucket size = min gap possible
• so, elements from different buckets must give us the answer
• all buckets have 1 exactly element - answer is gap
• Otherwise, atleast 1 bucket will be empty - answer is more than gap

20 8 15 12 min = 8 max = 20

max_gap = 20 - 8 = 12 min_gap = (20 - 8) / (4-1) = 4

now, create buckets of size 4 from min and max

---

comunicate with each other

ping the TA on flock

ping us

---

TA session tomorrow

1st week - just introductory stuff recording of this video will be up share notes