# Carry Forward & Subarrays

---
title: Pre Lecture Communication
description:
duration: 500
card_type: cue_card
---

Please share this message with the learners on Whasapp-
**Hi Learners!** 👩‍💻

**ABOUT THE NEXT SESSION - Carry Forward**

📚 In DSA, the carry-forward technique is like a magic wand ✨ that lets us reuse previously calculated results, saving time and effort.

🧮 This smart approach helps optimize Time Complexity 🚀 by avoiding redundant calculations.

📖 The session will feature some mind-blowing questions 💡 and promises to be engaging and super interesting. 🤩 Don’t miss out—see you all there!

---
title: Revision Quiz 1
description: Quiz 1
duration: 30
card_type: quiz_card
---

# Question
Calculate the prefix sum array for following array:-
`[10, 32, 6, 12, 20, 1]`

# Choices
- [x] [10,42,48,60,80,81]
- [ ] [10,42,49,60,79,81]
- [ ] [42,48,60,80,81,10]
- [ ] [15,43,58,61,70,82]

---
title: Revision Quiz 2
description: Quiz 2
duration: 30
card_type: quiz_card
---

# Question

What is the generalised equation to find the sum of elements from L to R ?

# Choices
- [x] sum[L R] = pf[R] - pf[L-1]
- [ ] sum[L R] = pf[R] - pf[L]
- [ ] sum[L R] = pf[R-1] - pf[L]
- [ ] sum[L R] = pf[R-1] - pf[L-1]

---
title: Revision Quiz 3
description: Quiz 3
duration: 30
card_type: quiz_card
---

# Question
What is the time taken to find sum of element from index L to R, assuming you have computed prefix sums array ?

# Choices
- [ ] O(N)
- [x] O(1)
- [ ] O(log(N))
- [ ] O(N^2^)

---
title: Contest Information
description:
duration: 180
card_type: cue_card
---

>Note to Instructor
1. Please motivate students about **Contest** which will happen at the end of the module.
2. It'll be of 1.5 hrs and will consists of 3 questions from topics that were taught in the module.
3. LET THEM KNOW ABOUT **IMPORTANCE OF CONTESTS**.
* It is **absolutely necessary** to give live contest no matter if you are confident in that topic or not, because it will help us understand what are the gaps in our understanding of the topics and how we can improvise it.
* After the live contest, discussion will happen with the instructor.
* Even If you fail live contest, no worries there is one more chance given as Re-attempt from Sat 12am to Sun 11:59pm.
5. Motivate for focusing on only **LIVE contest** and to depend on re-attempt only in an unavoidable cicumstances.
6. Tell them that if they solve Assignment regularly, then they will already at the time of Contest and quick revision will be more than enough.

---
title: Problem 1 Count of Pairs ag
description:
duration: 240
card_type: cue_card
---
Given a string **s** of lowercase characters, return the **count of pairs (i,j)** such that **i < j** and **s[ i ] is 'a'** and **s[ j ] is 'g'**.

### Example 1

String s = "abegag"
Ans = 3

### Explanation:
Here, [i,j] such that i<j and s[i] is 'a' and s[j] is 'g' are [0,3], [0,5] and [4,5]. So ans would be 3.

---
title: Quiz 1
duration: 45
card_type: quiz_card
---

# Question
What is the count of **a,g** pairs in the array:-
`s = "acgdgag"`

# Choices
- [x] 4
- [ ] 3
- [ ] 5
- [ ] 2

---
title: Quiz 1 Explanation
duration: 45
card_type: cue_card
---

**Explanation:**
Here, [i,j] such that i<j and s[i] is 'a' and s[j] is 'g' are [0,2], [0,4], [0,6] and [5,6]. So ans would be 4.

---
title: Quiz 2
duration: 60
card_type: quiz_card
---

# Question
How many **ag** pairs are in this string?
`s = "bcaggaag"`

# Choices
- [x] 5
- [ ] 4
- [ ] 3
- [ ] 6

---
title: Quiz 2 Explanation
duration: 45
card_type: cue_card
---

**Explanation:**
Here, [i,j] such that i<j and s[i] is 'a' and s[j] is 'g' are [2,3], [2,4], [2,7], [5,7] and [6,7]. So ans would be 5.

---
title: Problem 1 Brute Force Solution
description:
duration: 800
card_type: cue_card
---

For every **'a'**, we need to find the count of **g's** on the right side of **a**. So, we need to have nested loops.

### Pseudocode

function count_ag(str) {
    result = 0;
    for (i -> 0 to n-1) {
        if(str[i] == 'a'){
            for (j -> i+1 to N-1){
                if(str[j] == 'g') {
                    result++;
                }               
            }
        }
    }
    return result;
}

### Time and Space Complexity
-- TC - $O(n^2)$
-- SC - $O(1)$

---
title: Problem 1 Optimised solution
description:
duration: 1000
card_type: cue_card
---

### Observation:
* For every **'g'**, we need to know the count of **'a'** on left side of **'g'**.

* We will store the count of **'a'** and whenever **'g'** is encountered, we will add the count of **'a'** to the result.

### Dry Run
Example: **"acbagkagg"**

### Pseudocode

function count_ag(str) {
    result = 0;
    count_a = 0;
    for(i -> 0 to n-1) {
        if(str[i] == 'a') {     
            count_a++;          
        }
        else if(str[i] == 'g') {
            result += count_a;
        }
    }
    return result;
}

#### Time and Space Complexity

What will be T.C and S.C for this approach?
-- TC - $O(n)$
-- SC - $O(1)$

---
title: Introduction to Subarrays
description:
duration: 900
card_type: cue_card
---

### Definition
A subarray is a contiguous part of an array. It is formed by selecting a range of elements from the array. A subarray can have one or more elements and must be a contiguous part of the original array.

### Example
Consider the following array of integers:

| 4 | 1 | 2 | 3 | -1 | 6 | 9 | 8 | 12 |
| - | - | - | - | - | - | - | - | - |

* `2, 3, -1, 6` is a subarray of length 4.
* `9` is a subarray of single element.
* `4, 1, 2, 3, -1, 6, 9, 8, 12` is a subarray consisting of all the array elements.
* `4, 12` is **not** a subarray because loop does not count as subarray.
* `1, 2, 6` is **not** a subarray beacuse the array elements must be contiguous.
* `3, 2, 1, 4` is **not** a subarray because order of the elements in a subarray should be same as in the array.

---
title: Quiz 3
description:
duration: 45
card_type: quiz_card
---
# Question
A[] = { 2, 4, 1, 6, -3, 7, 8, 4}
Which of the following is a valid subarray?
# Choices
- [ ] {1, 6, 8}
- [ ] {1, 4}
- [ ] {6, 1, 4, 2}
- [x] {7, 8, 4}

---
title: Quiz 3 Explanation
description:
duration: 300
card_type: cue_card
---
**Explanation:** {1, 6, 8} & {1, 4} are not contiguous parts of array. {6, 1, 4, 2} is not in the same order as in original array. Only {7, 8, 4} is a valid subarray.

---
title: Representation of a Subarray
description: Representation of a Subarray
duration: 600
card_type: cue_card
---
#### Representation of a Subarray
A Subarray can be uniquely represented in following ways:
1. By specifying the `start` and `end` index of the subarray.
2. By specifying the `start` index and `length` of the subarray.

If we consider the same array from the above example,
| 4 | 1 | 2 | 3 | -1 | 6 | 9 | 8 | 12 |
| - | - | - | - | - | - | - | - | - |

The subarray `2, 3, -1, 6` can be represented as
* the range of elements starting at index `2` and ending at index `5` (0-based indexing).
* the range of elements having length of `4` with start index as `2`.

---
title: Quiz 4
description:
duration: 45
card_type: quiz_card
---
# Question
How many subarrays of the following array start from index 0
[4, 2, 10, 3, 12, -2, 15]
# Choices
- [ ] 6
- [x] 7
- [ ] 21
- [ ] 36

---
title: Quiz 4 Explanation
description:
duration: 300
card_type: cue_card
---

[4] (starting from index 0)
[4, 2]
[4, 2, 10]
[4, 2, 10, 3]
[4, 2, 10, 3, 12]
[4, 2, 10, 3, 12, -2]
[4, 2, 10, 3, 12, -2, 15]
Therefore, there are a total of 7 subarrays that start from index 0.

---
title: Quiz 5
description:
duration: 45
card_type: quiz_card
---
# Question
How many subarrays of the following array start from index 1
[4, 2, 10, 3, 12, -2, 15]
# Choices
- [x] 6
- [ ] 7
- [ ] 21
- [ ] 36

---
title: Quiz 5 Explanation
description:
duration: 300
card_type: cue_card
---
[2] (starting from index 1)
[2, 10]
[2, 10, 3]
[2, 10, 3, 12]
[2, 10, 3, 12, -2]
[2, 10, 3, 12, -2, 15]
Therefore, there are a total of 6 subarrays that start from index 1.

---
title: Formula to count total no. of subarrays
description:
duration: 600
card_type: cue_card
---
### Formula to count no. of subarrays
No. of subarrays starting from index 0 = n
No. of subarrays starting from index 1 = n-1
No. of subarrays starting from index 2 = n-2
No. of subarrays starting from index 3 = n-3
...........
...........
No. of subarrays starting from index n-1 = 1

So, Using the formula for the sum of an arithmetic series, total number of subarrays = n + (n-1) + (n-2) + (n-3) + . . . . . . + 3 + 2 + 1 = n(n+1)/2.

total = n(n + 1) / 2

---
title: Print the subarray of the array that starts from the start index and ends at the end index
description:
duration: 900
card_type: cue_card
---
### Problem Statement
Given an array of integers and two indices, a start index and an end index, we need to print the subarrays of the array that starts from the start index and ends at the end index (both inclusive).

### Solution
To solve this problem, we can simply iterate over the elements of the array from the start index to the end index (both inclusive) and print each element.

### Pseudocode

function printSubarray(arr[], start, end) {
    for (i -> start to end) {
        print(arr[i])
    }
    print("\n")
}

### Time and Space Complexity
What will be T.C and S.C for the above approach?
* TC - O(n)
* SC - O(1)

---
title: Print all possible subarrays of the array
description:
duration: 1200
card_type: cue_card
---
### Problem Statement:
Given an array of integers, we need to print all possible subarrays of the array.

### Example

Input: [1, 2, 3]
Output:
[1]
[1, 2]
[1, 2, 3]
[2]
[2, 3]
[3]

### Solution
To solve this problem, we can generate all possible subarrays of the array using two nested loops.
* The outer loop iterates over the starting index of the subarray.
* The inner loop iterates over the ending index of the subarray.
* At each iteration, we print the subarray from the starting index to the ending index.

### Pseudocode

function printSubarrays(arr[], n) {
    // Generate all possible subarrays
    for (i -> 0 to n-1) {
        for (j -> i to n-1) {
            // Print the current subarray
            for (k -> i to j) {
                print(arr[k])
            }
            cout << endl;
        }
    }
}

### TC & SC:
TC - O(N^3)
SC - O(1)

---
title: Problem 2 Max And Min
description:
duration: 240
card_type: cue_card
---

**Given an array of N integers, return the length of smallest subarray which contains both maximum and minimum element of the array.**

---
title: Quiz 6
duration: 60
card_type: quiz_card
---

## Question
What is the length of the smallest subarray that contains both the maximum and minimum values of the array?
`[2, 2, 6, 4, 5, 1, 5, 2, 6, 4, 1]`

## Choices
- [ ] 4
- [ ] 5
- [ ] 2
- [x] 3

---
title: Quiz 6 Explanation
duration: 45
card_type: cue_card
---

Answer: 3

From the Array, minimum element is 1 and maximum is 6. Smallest subarray which contains both is from index 8 to index 10 which is [6, 4, 1] of length 10-8+1=3.

### Another Example

A[ ] = { 1, 2, 3, 1, 3, 4, 6, 4, 6, 3}
Ans = 4

### Explanation:
Here, minimum element is 1 and maximum is 6. Smallest subarray which contains both is from index 3 to index 6 which is of length 6-3+1=4.

---
title: Problem 2 Brute Force Solution
description:
duration: 200
card_type: cue_card
---
Check all subarrays and find the answer.
-- TC - $O(n^3)$
-- SC - $O(1)$
Note: It can be reduced to $O(n^2)$ since we can check miniumum and maximum in a subarray in second loop itself.

---
title: Problem 2 Optimised Solution Observation
description:
duration: 800
card_type: cue_card
---
* The answer subarray must have exactly one instance of minimum element and one instance of maximum element since we want the length to be minimum.
* The minimum and maximum value must be present at the corners of the subarray.
* So, basically we are looking for subarray **which starts with maximum value and ends with closest minimum value or which starts with minimum value and ends with closest maximum value.**

### NOTE:
1. We can search a **min** for a **max** or vice versa, only in a single direction.
1. We don't have to consider all the pairs of min and max but look for closest pair, since we want to find smallest such subarray.
2. So we can keep track of the last found min and a last found max index.

### Dry Run

A[ ] = { 2, 2, 6, 4, 5, 1, 5, 2, 6, 4, 1 }

Initially,
last_min_index = **-1**
last_max_index = **-1**
ans = **INT_MAX**
minValue = **1**
maxValue = **6**

| i | A[i] | last_min_index |last_max_index|ans|
| -------- | -------- | -------- |-------- |-------- |
| 0| 2| -1| -1| INT_MAX |
| 1| 2| -1| -1| INT_MAX |
| 2| 6| -1| 2| INT_MAX |
| 3| 4| -1| 2| INT_MAX |
| 4| 5| -1| 2| INT_MAX |
| 5| 1| 5| 2| 5-2+1 = 4|
| 6| 5| 5| 2| 4|
| 7| 2| 5| 2| 4|
| 8| 6| 5| 8| 4|
| 9| 4| 5| 8| 4|
| 10| 1| 10| 8|10-8+1 = 3|

**So final ans would be 3.**

### Pseudocode

function minSubarray(A[], n)
{
    // find maximum and minimum
    // values in the array
    minValue = minOfArray(A);
    maxValue = maxOfArray(A);
    
    last_min_index = -1, last_max_index = -1, ans = INT_MAX;
    
    for(i -> 0 to n-1)
    {
        if(A[i] == minValue)
        {
            last_min_index = i;
            if(last_max_index != -1)
            {
                ans = min(ans, i-last_max_index+1);
            }
            
        }
        if(A[i] == maxValue) 
        {
            last_max_index = i;
            if(last_min_index != -1)
            {
                ans = min(ans, i-last_min_index+1);
            }
            
        }
        
    }
    return ans;
}

### Time and Space Complexity

What will be T.C and S.C for this approach?
-- TC - $O(n)$
-- SC - $O(1)$

---
title: MOTIVATION FOR NEXT CLASS
description:
duration: 800
card_type: cue_card
---
We'll discuss finding sum of all subarrays in different ways, finally leading to the optimised approach.

**Sliding Window**: It is important because it simplifies the process of solving array-related problems involving continuous subarrays or subsequences.

* The concepts learnt will be used throughout the course, so requesting all to not miss the session!

---
title: Summarise
description:
duration: 1800
card_type: cue_card
---
Please summarise the session quickly via notes.

---
title: Unlock Assignment
description:
duration: 600
card_type: cue_card
---
Please unlock the assignment for students by clicking this "question mark" button on top bar.
<img src="https://d2beiqkhq929f0.cloudfront.net/public_assets/assets/000/078/685/original/Screenshot_2024-06-19_at_7.17.12_PM.png?1718804854" width=300 />

Ask students to **SUBMIT ANYONE PROBLEM** from assignment right now and let you know.