Agenda

• Introduction to Array
• Dynamic Array
• Problem-solving

Array

An array is a data structure which stores homogenous (similar) data items. An array variable is used to store more than one data item of the same data type at contiguous memory locations.

Limitation of Array

The array is a static data structure with a fixed size and the size of the array should be known in advance so, the size of the array cannot be modified further and hence no modification can be done during runtime.
If the size of the declared array is more than the required size then, it can lead to memory wastage.

We can overcome this problem of fixed size by using Dynamic Arrays.

Dynamic Array

A dynamic array, often referred to as a resizable array or a growable array, is a data structure that allows elements to be added or removed, and it automatically resizes itself to accommodate new elements. This is in contrast to a static array, where the size is fixed and needs to be determined ahead of time.

Example of Dynamic Arrays
C++ - Vector
Java - ArrayList
Python - List

How Dynamic Array Works:

• Initial Allocation:
  When a dynamic array is created, it starts with a small initial size, often a default size like 10 or 16.
  The array is stored in a contiguous block of memory, similar to a static array.
• Adding Elements:
  As elements are added to the dynamic array, it checks whether there is enough space to accommodate the new element.
  If there is enough space, the new element is simply added at the next available position.
  If there is not enough space, the array needs to be resized to accommodate the new element.
• Resizing the Array:
  When the array needs to be resized, a new larger block of memory is allocated.
  The existing elements are then copied or moved to the new memory block.
  After resizing, the new element is added to the array.

How Size Expansion Works:

Doubling the Size:
A common strategy used in dynamic arrays is to double the size of the array when it needs to be resized.
This strategy is efficient because it reduces the frequency of resizing operations, which are relatively expensive in terms of time complexity.
Amortized Constant Time:

• Even though resizing the array involves copying the existing elements to a new memory block, the average time complexity for adding an element to a dynamic array is considered constant time, denoted as O(1).
• This is because the resizing operation occurs infrequently, and the cost of resizing is amortized over the many insertions that can be performed before the next resize is needed.

Time Complexity

Insertion
Best Case- O(1)
Worst Case-O(n) [If the dynamic array doesn't have any room for the new item, it will need to expand, which takes O(n) time.]

Deletion - O(n)

Problems

1. Max Value
Given an array of N positive integers. The task is to find the maximum value of |arr[i] – arr[j]| + |i – j|, where 0 <= i, j <= N – 1 and arr[i], arr[j] belong to the array.

Example
Input : N = 4, arr[] = { 4, 5, 6, 8 }
Output: 4
Explanation:
Choose i = 0 and j = 2. This will result in |4-8|+|0-3| = 7 which is the maximum possible value.

Brute Force Method
We can iterate in two for loops and get the maximum value for the expression.
Implementation in C++:

#include <bits/stdc++.h>
using namespace std;

int findMax(int arr[], int n)
{
  int ans = 0;
  for (int i = 0; i < n; i++)
    for (int j = 0; j < n; j++)
      ans = max(ans, abs(arr[i] - arr[j]) + abs(i - j));
  return ans;
}

int main()
{
  int n;
  cin >> n;
  int arr[n];
  for (int i = 0; i < n; i++)
    cin >> arr[i];
  cout << findMax(arr, n) << endl;
  return 0;
}

Implementation in Java:

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] arr = new int[n];
        
        for (int i = 0; i < n; i++) {
            arr[i] = sc.nextInt();
        }
        
        System.out.println(findMax(arr, n));
    }

    public static int findMax(int[] arr, int n) {
        int ans = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                ans = Math.max(ans, Math.abs(arr[i] - arr[j]) + Math.abs(i - j));
            }
        }
        return ans;
    }
}

Implementation in JavaScript

function findMaxValue(arr) {
    const n = arr.length;
    let maxValue = Number.NEGATIVE_INFINITY; // Initialize the maximum value as negative infinity

    // Iterate through all pairs of i and j
    for (let i = 0; i < n; i++) {
        for (let j = 0; j < n; j++) {
            // Calculate the expression |arr[i] - arr[j]| + |i - j|
            const currentValue = Math.abs(arr[i] - arr[j]) + Math.abs(i - j);
            // Update the maximum value
            maxValue = Math.max(maxValue, currentValue);
        }
    }

    return maxValue;
}

// Example Input
const arr = [4, 5, 6, 8];

// Find and display the maximum value
const result = findMaxValue(arr);
console.log("The maximum value is:", result);

Implementation in Python:

def findValue(arr, n): 
    ans = 0; 
      
    # Iterating two for loop,  
    # one for i and another for j. 
    for i in range(n): 
        for j in range(n): 
              
            # Evaluating |arr[i] - 
            # arr[j]| + |i - j| 
            # and compare with 
            # previous maximum. 
            ans = ans if ans>(abs(arr[i] - arr[j]) + 
                              abs(i - j)) else (abs(arr[i]-
                                    arr[j]) + abs(i - j)); 

    return ans;

Time Complexity : O(N^2)
Auxiliary Space: O(1)

Optimised Approach

After removing the mod signs the following 2 equation is formed and we have to find the maximum value of them-

• 1.(arr[i] + i) – (arr[j] + j)
• 2.(arr[i] – i) – (arr[j] – j)
  Now our task is easy, we just need to find the maximum difference between the two values of these two arrays.

Implementation in C++:

#include <bits/stdc++.h>
using namespace std;

int findMax(int arr[], int n)
{
  int temp1, temp2;
  int max1 = INT_MIN, max2 = INT_MIN;
  int min1 = INT_MAX, min2 = INT_MAX;
  for (int i = 0; i < n; i++)
  {
    temp1 = arr[i] + i;
    temp2 = arr[i] - i;
    max1 = max(max1, temp1);
    min1 = min(min1, temp1);
    max2 = max(max2, temp2);
    min2 = min(min2, temp2);
  }
  return max((max1 - min1), (max2 - min2));
}

int main()
{
  int n;
  cin >> n;
  int arr[n];
  for (int i = 0; i < n; i++)
    cin >> arr[i];
  cout << findMax(arr, n) << endl;
  return 0;
}

Implementation in Java:

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        int n = sc.nextInt();
        int[] arr = new int[n];
        
        for (int i = 0; i < n; i++) {
            arr[i] = sc.nextInt();
        }
        
        System.out.println(findMax(arr, n));
    }

    public static int findMax(int[] arr, int n) {
        int max1 = Integer.MIN_VALUE, max2 = Integer.MIN_VALUE;
        int min1 = Integer.MAX_VALUE, min2 = Integer.MAX_VALUE;

        for (int i = 0; i < n; i++) {
            int temp1 = arr[i] + i;
            int temp2 = arr[i] - i;

            max1 = Math.max(max1, temp1);
            min1 = Math.min(min1, temp1);
            max2 = Math.max(max2, temp2);
            min2 = Math.min(min2, temp2);
        }

        return Math.max(max1 - min1, max2 - min2);
    }
}

Implementation in JavaScript:

function findMaxValue(arr) {
    let n = arr.length;
    let max1 = -Infinity, min1 = Infinity;
    let max2 = -Infinity, min2 = Infinity;

    for (let i = 0; i < n; i++) {
        let value1 = arr[i] + i; // arr[i] + i
        let value2 = arr[i] - i; // arr[i] - i

        max1 = Math.max(max1, value1);
        min1 = Math.min(min1, value1);

        max2 = Math.max(max2, value2);
        min2 = Math.min(min2, value2);
    }

    return Math.max(max1 - min1, max2 - min2);
}

// Example Usage
let arr = [4, 5, 6, 8];
console.log("Maximum Value:", findMaxValue(arr)); // Output: 4

Implementation in Python:

import sys 

def findValue(arr, n): 
    temp1=0; 
    temp2=0; 
    max1 = -sys.maxsize; 
    max2 = -sys.maxsize; 
    min1 = sys.maxsize; 
    min2 = sys.maxsize; 
  
    # Calculating max1 , min1 and max2, min2 
    for i in range(n): 
        temp1 = arr[i] + i; 
        temp2 = arr[i] - i; 
        max1 = max(max1, temp1); 
        min1 = min(min1, temp1); 
        max2 = max(max2, temp2); 
        min2 = min(min2, temp2); 
      
    # required maximum ans is max of (max1-min1) and 
    # (max2-min2) 
    return max((max1 - min1), (max2 - min2)); 

Time Complexity : O(N)
Auxiliary Space: O(1)

2. Trapping Rain Water
Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it can trap after rain.
Example:

Input: n=12 height= [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6
Explanation:
The above elevation map (black section) is represented by an array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are trapped.

Brute force Method
For each index, find the amount of water that can be stored and we have to sum it up. If we observe the amount of water stored at a particular index is the minimum or maximum elevation to the left and right of the index minus the elevation at that index.
Implementation in C++:

#include <bits/stdc++.h>
using namespace std;

int trap(vector<int> &arr)
{
  int n = arr.size();
  int waterTrapped = 0;
  for (int i = 0; i < n; i++)
  {
    int j = i;
    int leftMax = 0, rightMax = 0;
    while (j >= 0)
    {
      leftMax = max(leftMax, arr[j]);
      j--;
    }
    j = i;
    while (j < n)
    {
      rightMax = max(rightMax, arr[j]);
      j++;
    }
    waterTrapped += min(leftMax, rightMax) - arr[i];
  }
  return waterTrapped;
}

int main()
{
  int n;
  cin >> n;
  vector<int> arr(n);
  for (int i = 0; i < n; i++)
    cin >> arr[i];
  cout << trap(arr) << endl;
}

Implementation in Java:

import java.util.Scanner;

public class TrappingRainWater {

    public static int trap(int[] arr) {
        int n = arr.length;
        int waterTrapped = 0;
        for (int i = 0; i < n; i++) {
            int j = i;
            int leftMax = 0, rightMax = 0;
            while (j >= 0) {
                leftMax = Math.max(leftMax, arr[j]);
                j--;
            }
            j = i;
            while (j < n) {
                rightMax = Math.max(rightMax, arr[j]);
                j++;
            }
            waterTrapped += Math.min(leftMax, rightMax) - arr[i];
        }
        return waterTrapped;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = scanner.nextInt();
        }
        System.out.println(trap(arr));
    }
}

Implementation in JavaScript

function trapRainWater(height) {
    let totalWater = 0; // To store the total amount of trapped water
    let n = height.length; // Length of the input array

    // Iterate through each bar (except the first and last, as they can't trap water)
    for (let i = 1; i < n - 1; i++) {
        let leftMax = 0, rightMax = 0;

        // Find the maximum height to the left of the current bar
        for (let j = 0; j <= i; j++) {
            leftMax = Math.max(leftMax, height[j]);
        }

        // Find the maximum height to the right of the current bar
        for (let j = i; j < n; j++) {
            rightMax = Math.max(rightMax, height[j]);
        }

        // Calculate water trapped at the current bar
        totalWater += Math.min(leftMax, rightMax) - height[i];
    }

    return totalWater;
}

// Example usage:
let height = [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1];
let totalWater = trapRainWater(height);
console.log("Total trapped rain water:", totalWater); // Output: 6

Implementation in Python:

def trap(arr):
    n = len(arr)
    waterTrapped = 0
    for i in range(n):
        j = i
        leftMax, rightMax = 0, 0
        while j >= 0:
            leftMax = max(leftMax, arr[j])
            j -= 1
        j = i
        while j < n:
            rightMax = max(rightMax, arr[j])
            j += 1
        waterTrapped += min(leftMax, rightMax) - arr[i]
    return waterTrapped

Time Complexity: O(N^2)
Space Complexity: O(1)

Better Approach

We can take 2 array prefix and suffix array and precompute the leftMax and rightMax for each index beforehand. Then use the formula min(prefix[I], suffix[i])-arr[i] to compute water trapped at each index.
Implementation in C++:

#include <bits/stdc++.h>
using namespace std;

int trap(vector<int> &arr)
{
  int n = arr.size();
  int prefix[n], suffix[n];
  prefix[0] = arr[0];
  for (int i = 1; i < n; i++)
  {
    prefix[i] = max(prefix[i - 1], arr[i]);
  }
  suffix[n - 1] = arr[n - 1];
  for (int i = n - 2; i >= 0; i--)
  {
    suffix[i] = max(suffix[i + 1], arr[i]);
  }
  int waterTrapped = 0;
  for (int i = 0; i < n; i++)
  {
    waterTrapped += min(prefix[i], suffix[i]) - arr[i];
  }
  return waterTrapped;
}

int main()
{
  int n;
  cin >> n;
  vector<int> arr(n);
  for (int i = 0; i < n; i++)
    cin >> arr[i];
  cout << trap(arr) << endl;
}

Implementation in Java:

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] arr = new int[n];
        
        for (int i = 0; i < n; i++) {
            arr[i] = sc.nextInt();
        }
        
        System.out.println(trap(arr));
    }
    
    public static int trap(int[] arr) {
        int n = arr.length;
        int[] prefix = new int[n];
        int[] suffix = new int[n];
        
        prefix[0] = arr[0];
        for (int i = 1; i < n; i++) {
            prefix[i] = Math.max(prefix[i - 1], arr[i]);
        }
        
        suffix[n - 1] = arr[n - 1];
        for (int i = n - 2; i >= 0; i--) {
            suffix[i] = Math.max(suffix[i + 1], arr[i]);
        }
        
        int waterTrapped = 0;
        for (int i = 0; i < n; i++) {
            waterTrapped += Math.min(prefix[i], suffix[i]) - arr[i];
        }
        
        return waterTrapped;
    }
}

Implementation in JavaScript:

function trapRainWater(height) {
    const n = height.length;
    if (n <= 2) return 0; // Not enough bars to trap water

    const leftMax = new Array(n).fill(0);
    const rightMax = new Array(n).fill(0);
    let totalWater = 0;

    // Compute the prefix max (left max)
    leftMax[0] = height[0];
    for (let i = 1; i < n; i++) {
        leftMax[i] = Math.max(leftMax[i - 1], height[i]);
    }

    // Compute the suffix max (right max)
    rightMax[n - 1] = height[n - 1];
    for (let i = n - 2; i >= 0; i--) {
        rightMax[i] = Math.max(rightMax[i + 1], height[i]);
    }

    // Calculate trapped water at each index
    for (let i = 0; i < n; i++) {
        totalWater += Math.min(leftMax[i], rightMax[i]) - height[i];
    }

    return totalWater;
}

// Example usage:
const height = [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1];
console.log("Total trapped rain water:", trapRainWater(height), "units");

Implementation in Python:

def trap(arr):
    n = len(arr)
    prefix = [0] * n
    suffix = [0] * n
    
    prefix[0] = arr[0]
    for i in range(1, n):
        prefix[i] = max(prefix[i - 1], arr[i])
    
    suffix[n - 1] = arr[n - 1]
    for i in range(n - 2, -1, -1):
        suffix[i] = max(suffix[i + 1], arr[i])
    
    waterTrapped = 0
    for i in range(n):
        waterTrapped += min(prefix[i], suffix[i]) - arr[i]
    
    return waterTrapped

Time Complexity: O(N)
Space Complexity: O(N)

Optimised Solution

We can take 2 pointers l(left pointer) and r(right pointer) pointing to the 0th and last index respectively. Take two variables leftMax and rightMax and initialise them to 0. If height[l] is less than or equal to height[r] then if leftMax is less than height[l] update leftMax to height[l] else add leftMax-height[l] to your final answer and move the l pointer to the right i.e l++. If height[r] is less than height[l], then now we are dealing with the right block. If height[r] is greater than rightMax, then update rightMax to height[r] else add rightMax-height[r] to the final answer. Now move r to the left. Repeat these steps till l and r cross each other.
Implementation in C++:

include <bits/stdc++.h>

using namespace std;
int trap(vector<int> &arr)
{
  int n = arr.size();
  int left = 0, right = n - 1;
  int res = 0;
  int maxLeft = 0, maxRight = 0;
  while (left <= right)
  {
    if (arr[left] <= arr[right])
    {
      if (arr[left] >= maxLeft)
      {
        maxLeft = arr[left];
      }
      else
      {
        res += maxLeft - arr[left];
      }
      left++;
    }
    else
    {
      if (arr[right] >= maxRight)
      {
        maxRight = arr[right];
      }
      else
      {
        res += maxRight - arr[right];
      }
      right--;
    }
  }
  return res;
}

int main()
{

  int n;
  cin >> n;
  vector<int> arr(n);
  for (int i = 0; i < n; i++)
    cin >> arr[i];
  cout << trap(arr) << endl;
}

Implementation in Java:

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] arr = new int[n];
        
        for (int i = 0; i < n; i++) {
            arr[i] = sc.nextInt();
        }
        
        System.out.println(trap(arr));
    }
    
    public static int trap(int[] arr) {
        int n = arr.length;
        int left = 0, right = n - 1;
        int res = 0;
        int maxLeft = 0, maxRight = 0;
        
        while (left <= right) {
            if (arr[left] <= arr[right]) {
                if (arr[left] >= maxLeft) {
                    maxLeft = arr[left];
                } else {
                    res += maxLeft - arr[left];
                }
                left++;
            } else {
                if (arr[right] >= maxRight) {
                    maxRight = arr[right];
                } else {
                    res += maxRight - arr[right];
                }
                right--;
            }
        }
        
        return res;
    }
}

Implementation in Javascript:

function trapRainWater(height) {
    let n = height.length;

    // Initialize two pointers
    let left = 0, right = n - 1;
    let leftMax = 0, rightMax = 0;
    let totalWater = 0;

    // Loop until the left and right pointers cross each other
    while (left <= right) {
        if (height[left] <= height[right]) {
            // Process the left side
            if (height[left] >= leftMax) {
                leftMax = height[left]; // Update leftMax
            } else {
                totalWater += leftMax - height[left]; // Add trapped water
            }
            left++; // Move left pointer to the right
        } else {
            // Process the right side
            if (height[right] >= rightMax) {
                rightMax = height[right]; // Update rightMax
            } else {
                totalWater += rightMax - height[right]; // Add trapped water
            }
            right--; // Move right pointer to the left
        }
    }

    return totalWater;
}

// Example usage:
let height = [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1];
let totalWater = trapRainWater(height);
console.log("Total trapped rain water:", totalWater); // Output: 6

Implementation in Python:

def trap(arr):
    n = len(arr)
    left, right = 0, n - 1
    res = 0
    maxLeft, maxRight = 0, 0
    
    while left <= right:
        if arr[left] <= arr[right]:
            if arr[left] >= maxLeft:
                maxLeft = arr[left]
            else:
                res += maxLeft - arr[left]
            left += 1
        else:
            if arr[right] >= maxRight:
                maxRight = arr[right]
            else:
                res += maxRight - arr[right]
            right -= 1
    
    return res

Time Complexity: O(N)
Space Complexity: O(1)