SAMSUNG 49-Inch Odyssey G9

Because earth is not flat

Description

The problem is to find the maximum subarray sum within a given array of integers.

Intuition

Initially, we can think of a brute force approach where we consider every possible subarray and calculate its sum. However, this approach would be inefficient for large arrays.

Approach

We can use Kadane's algorithm to solve this problem efficiently. Kadane's algorithm works by iterating through the array while keeping track of the maximum sum of subarrays ending at each position. The key idea is to decide whether to extend the current subarray by adding the next element to it or to start a new subarray at the current element. By maintaining a variable to store the maximum sum found so far (max_so_far) and another variable to store the maximum sum of subarrays ending at the current position (max_ending_here), we can compute the result in linear time.

Steps:

1. Initialize max_so_far and max_ending_here to the value of the first element of the array.
2. Iterate through the array starting from the second element:
   • Update max_ending_here as the maximum of the current element itself or the sum of max_ending_here and the current element.
   • Update max_so_far as the maximum of max_so_far and max_ending_here.
3. After iterating through the array, max_so_far will contain the maximum subarray sum.

Complexity

Time Complexity:

O(n), where n is the number of elements in the array. We iterate through the array once.

Space Complexity:

O(1), since we only use a constant amount of extra space.

Code

C++

class Solution {
public:
    int numIslands(vector<vector<char>>& grid) {
        if (grid.empty() || grid[0].empty()) {
            return 0;
        }
    
        int rows = grid.size();
        int cols = grid[0].size();
        int islands = 0;
        vector<pair<int, int>> directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        function<void(int, int)> dfs = [&](int row, int col) {
            if (row < 0 || row >= rows || col < 0 || col >= cols || grid[row][col] != '1') {
                return;
            }
            grid[row][col] = '0';
            for (auto& dir : directions) {
                int newRow = row + dir.first;
                int newCol = col + dir.second;
                dfs(newRow, newCol);
            }
        };
        for (int row = 0; row < rows; ++row) {
            for (int col = 0; col < cols; ++col) {
                if (grid[row][col] == '1') {
                    dfs(row, col);
                    islands++;
                }
            }
        }
        return islands;
    }
};

Python

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        if not grid or not grid[0]:
            return 0
        
        rows = len(grid)
        cols = len(grid[0])
        islands = 0
        
        def dfs(row, col):
            if row < 0 or row >= rows or col < 0 or col >= cols or grid[row][col] != '1':
                return
            grid[row][col] = '0'  # Mark current cell as visited
            
            # Recursively visit all four possible directions
            dfs(row - 1, col)  # Up
            dfs(row + 1, col)  # Down
            dfs(row, col - 1)  # Left
            dfs(row, col + 1)  # Right
        
        # Traverse each cell in the grid
        for row in range(rows):
            for col in range(cols):
                if grid[row][col] == '1':
                    # Found a new island, initiate DFS to mark all connected land cells
                    dfs(row, col)
                    islands += 1
        
        return islands

Java

class Solution {
    public int numIslands(char[][] grid) {
        if (grid == null || grid.length == 0 || grid[0].length == 0) {
            return 0;
        }
        
        int rows = grid.length;
        int cols = grid[0].length;
        int islands = 0;
        
        // Directions for moving in 4 possible directions (up, down, left, right)
        int[][] directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        
        // Depth-First Search (DFS) function to mark connected land cells
        for (int row = 0; row < rows; ++row) {
            for (int col = 0; col < cols; ++col) {
                if (grid[row][col] == '1') {
                    // Found a new island, initiate DFS to mark all connected land cells
                    islands++;
                    dfs(grid, row, col, directions);
                }
            }
        }
        
        return islands;
    }
    
    private void dfs(char[][] grid, int row, int col, int[][] directions) {
        // Check boundaries and if current cell is land ('1')
        if (row < 0 || row >= grid.length || col < 0 || col >= grid[0].length || grid[row][col] != '1') {
            return;
        }
        
        // Mark current cell as visited by setting it to '0'
        grid[row][col] = '0';
        
        // Recursively visit all four possible directions
        for (int[] dir : directions) {
            int newRow = row + dir[0];
            int newCol = col + dir[1];
            dfs(grid, newRow, newCol, directions);
        }
    }
}

JavaScript

var numIslands = function(grid) {
    if (!grid.length || !grid[0].length)
        return 0;
    const rows = grid.length;
    const cols = grid[0].length;
    let islands = 0;
        console.log("begin grid", grid)
    const dfs = (row, col) => {
        if (row < 0 || col < 0 || row >= rows || col >= cols || grid[row][col] !== '1')
            return;
        grid[row][col] = '0';
        
        dfs(row - 1, col);
        dfs(row + 1, col);
        dfs(row, col - 1);
        dfs(row, col + 1);
    };
    for (let row = 0; row < rows; row++) {
        for (let col = 0; col < cols; col++) {
            if (grid[row][col] === '1') {
                dfs(row, col);
                islands++;
            }
        }}
        console.log("islands", islands)
        console.log("grid", grid)
    return islands;
};