Lecture 23: Introduction to 2D Arrays in C++ || LeetCode Questions

Name: Lecture 23: Introduction to 2D Arrays in C++ || LeetCode Questions
Uploaded: 2021-12-20T06:50:40.000Z
Duration: 3 h 36 s

Introduction to 2D Arrays

Overview of the Video

This video is presented by Love Babbar on the CodeHelp channel, focusing on 2D arrays. The discussion will cover what a 2D array is, its necessity, and how it differs from linear arrays.

The session aims to provide insights into memory storage for 2D arrays and practical applications such as binary search in this context. It promises an engaging learning experience with relatable examples.

Understanding 2D Arrays through Examples

A childhood game of tic-tac-toe (0 and X) serves as a simple introduction to the concept of a 2D array, illustrating how it consists of multiple cells arranged in rows and columns.

The speaker emphasizes that while implementing a small grid (3x3) can be straightforward using three separate arrays, scaling up to larger grids (like 10x10 or even 1000x1000) presents challenges that necessitate a more efficient approach.

Memory Storage for 2D Arrays

Visualizing Data Structure

To manage larger datasets efficiently, the speaker suggests creating a linear array instead of multiple individual arrays for each row when dealing with extensive data like a table with many rows and columns. This method simplifies implementation while maintaining clarity in structure.

An example is provided where a linear array with nine cells represents a visual grid of three rows and three columns, demonstrating how values can be accessed via index mapping rather than traditional multi-dimensional structures.

Mathematical Mapping Formula

The formula for accessing elements within the linear representation of a 2D array is introduced: index = column * i + j, where i represents the row index and j represents the column index. This mathematical approach allows seamless navigation through stored data without needing complex structures.

Specific examples illustrate how to apply this formula effectively; for instance, calculating indices based on given row and column positions helps visualize data access in memory while reinforcing understanding of underlying mechanics.

Practical Applications & Conclusion

Transitioning from Theory to Practice

The speaker highlights that although viewers may grasp theoretical concepts about mapping indices in memory, there are existing implementations that simplify these processes without manual calculations or mappings required by users themselves. This realization underscores advancements in programming practices regarding data handling efficiency.

This structured overview encapsulates key discussions around understanding and utilizing 2D arrays effectively within programming contexts while providing timestamps for easy reference back to specific parts of the video content.

Understanding 2D Arrays in C++

Creating a 2D Array

A 2D array can be visualized as a matrix, but it is stored in memory as a linear array. For example, declaring int arr creates an array with 3 rows and 3 columns.

The syntax int arr indicates the creation of a two-dimensional array where '3' represents both the number of rows and columns.

After declaration, the structure consists of three rows (0th, 1st, and 2nd) and three columns (0th, 1st, and 2nd).

Internally, this structure is still represented as a linear array; however, users should focus on its matrix representation for practical purposes.

Inputting Values into a 2D Array

To take input for a simple one-dimensional array, we use cin >> arr[i];. This concept extends to two-dimensional arrays using cin >> arr[i][j];.

The method for taking input remains straightforward: iterate through each row and column to fill the values.

Outputting Values from a 2D Array

Outputting values from a one-dimensional array uses cout << arr[i];, while for two-dimensional arrays it becomes cout << arr[i][j];.

Understanding indices is crucial; for instance, arr refers to the element at the second index of row and first index of column.

Looping Through Rows and Columns

To execute input collection in a two-dimensional array effectively, nested loops are employed:

Outer loop iterates over rows (for(int i = 0; i < number_of_rows; i++))

Inner loop iterates over columns (for(int j = 0; j < number_of_columns; j++))

This approach ensures that all elements are filled correctly based on their respective indices.

Printing Values from the Array

Similar nested loops are used to print values:

Iterate through each row with an outer loop,

Use an inner loop to access each column's value.

Row-wise vs Column-wise Input

When collecting data in row-major order (row-wise), you would typically have your outer loop iterate over rows first. Conversely:

If you want column-major order (column-wise), switch the loops so that the outer loop iterates over columns first.

Hardcoding Values into Arrays

Understanding 2D Arrays and Functions in C++

Initializing a 2D Array

The speaker discusses how to initialize a 2D array, demonstrating with int arr=1,11,111,1111,2,22,222,2222,3,33,333,3333,4,44,444,4444;.

Acknowledges the limitation of having only three rows in the initialized array and removes an extra row before printing the elements.

Input Methods and Function Creation

Explains two methods for initializing arrays: hardcoding values or taking input row-wise and column-wise.

Introduces a function named search() to find an element within the array by prompting user input for the target value.

Searching Elements in the Array

The speaker mentions creating a function called isPresent() to check if a target exists in the array.

Demonstrates how to use this function with conditional statements to print whether an element is found or not.

Understanding Function Parameters

Discusses defining the isPresent function with parameters but encounters errors due to unspecified column sizes.

Clarifies that specifying column size is necessary in C++ when passing arrays as parameters.

Implementing Search Logic

Describes how to traverse through each element of the array comparing it with the target value using conditional checks.

Finalizes the search logic by returning true if an element matches and false otherwise.

Implementing Row-Wise Sum Calculation

Introduction to Row-Wise Sum

The speaker transitions into calculating row-wise sums from a given matrix example (e.g., summing elements like 3+4+11).

Function Development for Summation

Mentions writing a function printSum(int arr[], int row, int col) aimed at calculating and printing row-wise sums.

Loop Implementation for Summation

Explains using nested loops where one loop iterates over rows while another calculates sums of individual rows.

Testing and Debugging Code

Adjustments are made based on input dimensions (changing from 4x4 to 3x3), ensuring correct functionality during testing phases.

Final Output Verification

How to Calculate Row and Column Sums in a 2D Array?

Implementing Row and Column Sum Functions

The speaker introduces the concept of calculating row-wise sums in a 2D array, suggesting that for column-wise sums, one should iterate through columns first.

A nested loop structure is proposed: the outer loop iterates over columns while the inner loop iterates over rows to compute sums.

After correcting function names and running the code, it successfully outputs column sums as 12, 24, and 19.

The process of calculating column-wise sums is confirmed to be straightforward; each column's sum is derived from executing the loops correctly.

Finding the Largest Row Sum

The next task involves determining which row has the largest sum. In this case, it identifies that row 2 (index 1) has the maximum sum of 22.

A function largestRowSum(int arr[], int row, int col) is introduced to calculate both the largest row sum and its corresponding index.

The variable maxi is initialized to store maximum values found during iteration through each row's sum calculations.

An update mechanism for tracking which row has the maximum sum is discussed; if a new max is found, it updates both maxi and rowIndex.

Debugging and Finalizing Code

The speaker emphasizes commenting out unnecessary code before final execution of largestRowSum().

Upon running tests with inputs, an error in returning indices was identified; adjustments were made to ensure correct output.

After debugging, successful execution confirms that maximum row sum index is indeed at index 2 with a value of 22.

What Is Wave Order Printing in a 2D Array?

Understanding Wave Order Printing

The speaker presents a problem involving wave order printing of elements in a given n*m sized 2D array—first top-to-bottom for odd columns then bottom-to-top for even ones.

An example illustrates how elements are printed: starting from top down on even indexed columns followed by bottom up on odd indexed ones.

Coding Wave Order Logic

Discussion shifts towards implementing this logic using loops; understanding how vectors can represent arrays similarly aids comprehension.

It’s noted that odd-indexed columns require upward traversal while even-indexed ones necessitate downward traversal during printing operations.

Implementation Steps

To implement wave order printing effectively:

Use an outer loop for iterating through all columns,

Check if current column index is odd or even,

Utilize appropriate loops based on index parity for element access (top-down or bottom-up).

Example Loop Structures

For bottom-to-top:

for(int row=nRows−1; row>=0; row--) cout<< arr[row][col]<<endl;

For top-to-bottom:

for(int row =0;row<nRows;row++) cout<< arr[row][col]<< " ";

Debugging Code and Understanding Complexity

Debugging Process

The speaker encounters a spelling error in the code related to "vector" and expresses frustration over receiving incorrect answers.

A custom test is initiated to identify mistakes, with the speaker emphasizing careful examination of printed outputs before re-running the code.

After confirming that only cout was executed, the speaker prepares to submit the solution for correctness verification.

Time Complexity Analysis

The logic of the implemented code is confirmed as correct; complexity analysis reveals an O(n*m) time complexity due to traversing each element once.

Clarification on variables: n represents rows and m represents columns, highlighting that this type of problem frequently appears in online tests.

Introduction to Spiral Printing

Importance of Spiral Print

The spiral printing question is noted for its frequent appearance in interviews, particularly at companies like Amazon.

An example matrix (1 2 3, 4 5 6, 7 8 9) illustrates how elements should be printed in a spiral order.

Approach to Solve Spiral Print

The desired output sequence for spiral print is outlined: starting from the top row and moving clockwise around the matrix.

The speaker encourages viewers to think critically about their approach while reiterating that it’s a straightforward task.

Step-by-Step Implementation Strategy

Initial Steps

The first step involves printing the first row of the matrix.

Next, focus shifts to printing elements from the ending column while ensuring no duplicates are printed.

Traversal Logic

A systematic approach is described: print starting row, ending column, ending row, and starting column sequentially while adjusting boundaries after each pass.

Code Structure and Execution

Setting Up Variables

Initialization begins with determining number of rows (int row = matrix.size();) and columns (int col = matrix.size();).

Looping Through Elements

A loop structure (while(count < total)), tracks how many elements have been printed until all are processed.

Printing Logic Implementation

Spiral Matrix Printing and Binary Search in 2D Arrays

Spiral Matrix Printing Logic

The process of printing a matrix involves multiple parts, starting with the ending row and moving to the starting column. The explanation begins with how to print from the ending row to the starting row using a loop.

A for loop is introduced to iterate from endingRow down to startingRow, pushing elements into an answer vector (ans) as it goes. The startingCol is then incremented.

It’s noted that a count variable must be incremented each time an element is printed within all loops, emphasizing the importance of tracking how many elements have been processed.

An error arises due to incorrect spelling of "total" and capitalization issues in variable names, which are corrected before re-running the code.

After fixing errors, it’s confirmed that adding a condition (count < total) prevents duplicate entries during printing. This leads to successful execution of the code.

Complexity Analysis

The final implementation runs successfully and efficiently, achieving 100% faster performance. The complexity is analyzed as O(n*m), where n represents rows and m represents columns, indicating that each element is traversed only once.

The logic behind spiral printing involves four loops: one for each direction (left-to-right, top-to-bottom, right-to-left, bottom-to-top).

Emphasis on not needing to memorize complex patterns; understanding what needs to be printed suffices for implementing spiral printing effectively.

Homework Assignment: Rotating a Matrix

A common problem presented as homework involves rotating a given matrix by 90 degrees. An example matrix (1 2 3; 4 5 6; 7 8 9) illustrates this task.

Students are encouraged to take their time (up to 1.5 hours if needed) while solving this problem independently as it reinforces understanding of two-dimensional arrays.

Introduction to Binary Search in 2D Arrays

Transitioning from spiral printing, binary search will now be explored within two-dimensional arrays after previously learning it in one-dimensional arrays.

Assurance is given that no topics will be skipped; everything will be taught at appropriate times throughout the course material.

Searching in Sorted Matrices

A new question regarding searching within a sorted matrix introduces specific properties: integers are sorted row-wise and each first integer of every row exceeds the last integer of previous rows.

An example matrix (1 3 5 7; 10 11 16 20; etc.) demonstrates these properties clearly while setting up for an efficient search algorithm based on these characteristics.

By representing this matrix linearly (1,3,5,...), it's established that binary search can indeed be applied since it forms a sorted array structure suitable for such algorithms.

Implementing Binary Search Logic

Explanation continues on how binary search can be implemented by defining start and end indices based on rows and columns within the matrix context.

Binary Search in a 2D Array

Understanding the Binary Search Cases

The first case checks if the middle element (arr[mid]) equals the target; if true, it returns the index.

The second case determines if arr[mid] is less than the target, indicating that the search should continue in the right half of the array by updating start = mid + 1.

Conversely, if arr[mid] is greater than the target, it updates end = mid - 1, focusing on the left half.

Implementing Binary Search in Code

The code begins by determining matrix dimensions: int row = matrix.size(); int col = matrix.size();.

A while loop is initiated to perform binary search as long as start <= end. It addresses how to find an element in a 2D array using calculated midpoints.

Accessing Elements in a 2D Matrix

To fetch an element from a specific index (e.g., index of 16), one must determine its row and column indices based on its linear position.

For example, dividing an index by the number of columns helps identify which row contains that element.

Calculating Row and Column Indices

Using integer division (mid / col) gives us the row index for any given linear index.

The column index can be found using modulo operation (mid % col), ensuring values remain within valid column bounds.

Finalizing and Testing Code Execution

After implementing and testing all cases, successful execution leads to submission with a performance acceptance rate of 74.63%.

The process emphasizes understanding binary search application on a 2D array, highlighting ease except for line calculations related to indexing.

Clarifying Index Mapping Concepts

Line calculations are crucial; knowing both row and column indices allows effective access to elements within a matrix.

Understanding how linear indices map into two-dimensional arrays is essential for efficient searching.

Observations on Index Calculation Techniques

Dividing by column size yields quotient results representing row numbers while modulo provides precise positions within those rows.

This method simplifies finding indices across various scenarios when working with sorted matrices.

Complexity Analysis of Binary Search Implementation

Understanding Time Complexity in 2D Matrix Search

Introduction to Time Complexity

The size of a matrix is defined as row * column, leading to a time complexity of O(log(n)), where n equals row * column. Thus, the overall complexity can be expressed as O(log(m*n)).

Binary Search in Sorted Matrices

The discussion transitions to binary search, emphasizing that the matrix is sorted both row-wise and column-wise.

Acknowledges the challenge of arranging elements into a linear array due to unsorted sequences, indicating the need for alternative strategies.

Identifying Patterns for Searching

Introduces an example with a target value (10), prompting exploration of how to discard unnecessary elements based on comparisons.

Highlights that if the current element (9) is less than the target (10), it does not guarantee that all preceding elements are irrelevant.

Establishing Conditions for Search

Outlines case scenarios for searching within the matrix:

Case 1: If arr[mid] == target, return it as found.

Case 2: If arr[mid] < target, increment row index (row++).

Reducing Search Space

Discusses how identifying conditions allows for reducing search space effectively. For instance, if arr[mid] < target, we can move downwards in rows.

Conversely, if arr[mid] > target, it indicates that potential answers lie before this mid-point; thus, decrementing column index (col--) is necessary.

Implementing the Search Algorithm

Questions arise about coding implementation after establishing mid-points and search conditions.

Emphasizes starting from specific points in the matrix rather than arbitrary locations to ensure effective application of logic.

Starting Point Selection

Suggestion made to start from the last element of the first row (15). This choice guarantees efficient elimination of columns or rows based on comparisons with other elements.

Finalizing Code Logic

Describes setting up initial variables such as row and column indices before entering a while loop for searching through the matrix.

Executing and Testing Code

Concludes with executing test cases successfully, achieving an accuracy rate of 99.09%. Reflective commentary suggests that practice may enhance understanding among learners who struggled initially.

Overcoming Fear in Learning DSA

Embracing Challenges

The speaker encourages learners not to be afraid, emphasizing that fear will hinder progress and prevent them from completing the remaining videos on Data Structures and Algorithms (DSA).

Learners are advised to seek solutions independently rather than relying solely on spoon-feeding; they should engage with discussion forums for deeper understanding.

Understanding 2D Arrays

Key concepts covered include creating, initializing, and printing 2D arrays. The speaker highlights the importance of calculating sums of rows and columns.

Techniques learned include obtaining row-wise and column-wise input, as well as methods for wave printing, spiral printing, and rotating arrays by 90 degrees.

Practical Application

To solidify understanding of 2D arrays, learners are encouraged to solve at least ten problems related to this topic on platforms like LeetCode.