Scribd
Upload
6 views2 pages

Lecture 19 Advanced Problem Solving in 2D Arrays

Lecture 19 focuses on advanced problem solving in 2D arrays, covering key problems such as finding the row with the maximum number of 1s in a boolean 2D array and rotating a square matrix by 90 degrees clockwise. The lecture presents both naive and optimized approaches for the row problem, emphasizing a time complexity of O(N+M) for the optimized method. It also details the transformation logic for rotating a matrix, including transposing and reversing rows.

Uploaded by

abhijitdevgharetemp
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
6 views2 pages

Lecture 19 Advanced Problem Solving in 2D Arrays

Lecture 19 focuses on advanced problem solving in 2D arrays, covering key problems such as finding the row with the maximum number of 1s in a boolean 2D array and rotating a square matrix by 90 degrees clockwise. The lecture presents both naive and optimized approaches for the row problem, emphasizing a time complexity of O(N+M) for the optimized method. It also details the transformation logic for rotating a matrix, including transposing and reversing rows.

Uploaded by

abhijitdevgharetemp
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

2/13/26, 5:22 AM

Lecture 19 is titled "Advanced Problem Solving in 2D Arrays".

This lecture delves deeper into solving more complex problems using 2D Vectors
(dynamic 2D arrays).

Key Problems Covered:

1. Row with Maximum Number of 1s:

Problem Statement: Given a boolean 2D array where each row is sorted (0s
followed by 1s), find the row index with the maximum number of 1s.

Naive Approach: Iterate through every row, count the 1s, and keep track of the
maximum. (Time Complexity: O(N*M) ).
Optimized Approach (exploiting sorted property):
Find the index of the first 1 in the first row. Let's say it's at index j .
Move to the next row. Check if there is a 1 to the left of index j (i.e., at j-1 ).
If yes, update the leftMostOne index to j-1 and update the maxRowIndex .
Continue moving left until you hit a 0.
If no, simply move to the next row without changing the column index.
This allows you to traverse the matrix in a staircase manner from top-right to
bottom-left. (Time Complexity: O(N+M) ).

2. Rotate a Matrix by 90 Degrees (Clockwise):

Problem Statement: Given a square matrix, rotate it 90 degrees clockwise in-


place (without using extra space).

Transformation Logic:

The first row becomes the last column.

The last row becomes the first column.

Approach:

1. Transpose the Matrix: Swap elements matrix[i][j] with matrix[j][i] . Note: Only
swap the upper triangle with the lower triangle (i.e., j > i ) to avoid double-
swapping.

Generated with [Link]


2/13/26, 5:22 AM

2. Reverse Every Row: After transposing, reverse each row of the matrix. This
achieves the 90-degree rotation.

The lecture emphasizes visualizing these transformations and using pen and paper
to derive the logic before coding.

Here is the link to the lecture: Advanced Problem Solving in 2D Arrays | Lecture 19

Generated with [Link]

You might also like