Definition
A 2D array, also known as a matrix or an array of arrays, is a data structure that stores
elements in a grid-like format, organized by rows and columns. Conceptually, it represents
a table of values where each element is uniquely identified by two indices: one for its row
and one for its column. It's a collection of elements where each element itself is an array.
Example
Consider a 3x3 matrix representing a simple tic-tac-toe board:
```
[
['X', 'O', ' '],
[' ', 'X', 'O'],
['O', ' ', 'X']
]
```
Here, the element at row 0, column 0 is 'X', and the element at row 1, column 2 is 'O'.
Best Approach/Algorithm
The best approach for most fundamental operations on a 2D array, such as traversal,
accessing, or modifying elements, typically involves using nested loops.
* **Traversal**: To visit every element, an outer loop iterates through each row, and an
inner loop iterates through each column within that row.
* **Access**: To access a specific element, direct indexing `array[rowIndex][colIndex]` is
the most efficient method, providing O(1) access time.
* **Modification**: Similar to access, direct indexing is used to modify an element:
`array[rowIndex][colIndex] = newValue`.
Best Algorithm for Worst Cases
For basic operations like traversal, element access, or simple modification of a 2D array,
the standard nested loop approach (for traversal) and direct indexing (for
access/modification) are inherently the most optimal. There isn't a different algorithm that
performs better in "worst-case scenarios" for these fundamental tasks, as the complexity is
dictated by the dimensions of the array itself. For example, to visit every element in an `M x
N` matrix, you *must* perform `M * N` operations. Any algorithm aiming to do this will
necessarily have a time complexity of at least O(M*N). Therefore, the standard nested loop
approach already achieves this optimal lower bound.
Time Complexity and Space Complexity
* **Time Complexity**:
* **Accessing/Modifying a specific element**: O(1)
* **Traversing all elements (e.g., printing, summing)**: O(rows * columns) or O(M*N) for
an M x N matrix.
* **Searching for an element (unoptimized linear search)**: O(rows * columns) or
O(M*N).
* **Space Complexity**:
* **Storing the 2D array itself**: O(rows * columns) or O(M*N), as it requires space
proportional to the number of elements it holds.
* **Auxiliary space for operations (e.g., traversal)**: O(1) (excluding the input array and
any potential output array).
Real-time Examples with Coding Solution and Explanation
**Real-world Use Case**: Image processing often involves treating images as 2D arrays
(matrices) of pixel values. A common operation is to "flip" an image horizontally. This
means reversing the order of pixels in each row.
**Problem**: Given a binary matrix (an image where each pixel is either 0 or 1,
representing black or white), flip the image horizontally, then invert it (0 becomes 1, and 1
becomes 0).
**Example Input**:
```
[[1,1,0],[1,0,1],[0,0,0]]
```
**Expected Output (after horizontal flip then invert)**:
1. **Horizontal Flip**:
```
[[0,1,1],[1,0,1],[0,0,0]]
```
2. **Invert**:
```
[[1,0,0],[0,1,0],[1,1,1]]
```
Code without any library usage
```javascript
/**
* Flips a binary image horizontally and then inverts its pixels.
*
* A binary image is represented as a 2D array of integers, where each integer is 0 or 1.
* Flipping horizontally means that each row of the image is reversed.
* Inverting means that every 0 becomes 1, and every 1 becomes 0.
*
* @param {number[][]} image The input binary image (2D array).
* @returns {number[][]} The transformed image.
*/
function flipAndInvertImage(image) {
const numRows = [Link];
if (numRows === 0) {
return []; // Handle empty image
}
const numCols = image[0].length;
// Iterate through each row of the image
for (let r = 0; r < numRows; r++) {
// For each row, we need to flip it horizontally.
// We use two pointers, 'left' starting from the beginning
// and 'right' starting from the end of the row.
let left = 0;
let right = numCols - 1;
while (left <= right) {
// Swap elements at left and right pointers
// Temporarily store the left element
const temp = image[r][left];
image[r][left] = image[r][right];
image[r][right] = temp;
// After swapping, we also need to invert the pixels.
// If the values were 0 and 1, after swap they are still 0 and 1 (just positions
changed).
// We invert them in their *new* positions.
// A common trick for binary inversion is 1 - pixel_value.
image[r][left] = 1 - image[r][left];
if (left !== right) { // Avoid double-inverting the middle element if odd number of
columns
image[r][right] = 1 - image[r][right];
}
// Move pointers towards the center
left++;
right--;
}
}
return image; // Return the modified image
}
// Example Usage:
const image1 = [[1,1,0],[1,0,1],[0,0,0]];
Explanation for the code
1. **Function Definition**: The `flipAndInvertImage` function takes a 2D array `image` as
input.
2. **Edge Case Handling**: It first checks if the `image` is empty (`numRows === 0`). If so,
it returns an empty array to prevent errors.
3. **Dimensions**: It determines the number of rows (`numRows`) and columns
(`numCols`) from the input image. Assuming a rectangular matrix, all rows will have the
same number of columns.
4. **Row Iteration**: The code uses an outer `for` loop (`for (let r = 0; r < numRows; r++)`)
to iterate through each row of the 2D array.
5. **Horizontal Flip and Invert per Row**: Inside the outer loop, for each row `r`, we
perform two operations:
* **Two-Pointer Approach for Flipping**: Two pointers, `left` (starting at 0) and `right`
(starting at `numCols - 1`), are used to traverse the current row from both ends towards the
center. The `while (left <= right)` loop continues as long as `left` has not crossed `right`.
* **Swap**: Inside the `while` loop, the elements at `image[r][left]` and `image[r][right]`
are swapped. This effectively reverses the row horizontally.
* **Invert**: Immediately after swapping, or if `left` and `right` point to the same element
(in case of an odd number of columns), the values are inverted. A simple way to invert a
binary number (0 or 1) is to subtract it from 1 (e.g., `1 - 0 = 1`, `1 - 1 = 0`).
* `image[r][left] = 1 - image[r][left];` inverts the element that ended up at the `left`
position.
* `if (left !== right) { image[r][right] = 1 - image[r][right]; }` inverts the element that
ended up at the `right` position. The `if` condition is crucial to avoid double-inverting the
middle element when `numCols` is odd and `left` and `right` meet in the middle.
* **Pointer Movement**: After processing, `left` is incremented and `right` is
decremented to move towards the center of the row.
6. **Return Value**: After all rows have been processed, the modified `image` (which is
modified in-place) is returned.
The time complexity for this solution is O(R * C) where R is the number of rows and C is
the number of columns, because every element is visited and potentially modified exactly
once. The space complexity is O(1) auxiliary space, as modifications are done in-place
without using additional data structures proportional to the input size.
Interview Questions based on Companies
1. **Rotate Image (Matrix)** - Given an `n x n` 2D matrix representing an image, rotate the
image by 90 degrees (clockwise). You have to rotate the image in-place, which means you
modify the input 2D matrix directly. Do NOT allocate another 2D matrix. (Google, Amazon,