Solving LeetCode's Number of Islands: A Deep Dive into DFS

benono — Sat, 30 Nov 2024 00:27:51 +0000

Introduction

The Number of Islands problem is a classic example of depth-first search (DFS) application in grid traversal. In this article, I'll walk you through my thought process and implementation strategy.

Let me explain my approach to the Number of Islands problem.

Problem Understanding

This problem can be categorized as a grid traversal pattern where we need to:

Count the number of distinct islands
Define an island as a group of connected '1's
Handle the grid modification efficiently

Approach

I'll use DFS (Depth-First Search) for this problem because:

It's a natural fit for exploring connected components
We can modify the input grid to track visited cells
It provides a clean recursive solution

Implementation Strategy

Let me break down the key components:

Main Function:

Iterate through each cell in the grid
When we find a '1', increment our island counter
Start DFS exploration from that cell

DFS Helper Function:
- Check boundary conditions
- Verify if current cell is part of an island
- Mark visited cells
- Explore in all four directions

Edge Cases

Empty grid
Single row/column grid
Grid with no islands
Grid with all islands

Complexity Analysis

Time: O(M × N) where M is rows and N is columns
Space: O(M × N) worst case for the recursion stack

Key Optimization

Instead of using a separate visited set, we modify the input grid directly by marking visited cells with a different value. This approach:

Saves space
Simplifies our logic
Maintains the connected component property

My Implementation

/**
 * @param {character[][]} grid
 * @return {number}
 */
var numIslands = function (grid) {
  // We start with a counter and grid size
  var count = 0;
  const y = grid.length;
  const x = grid[0].length;
  // Handles the recursive exploration
  function dfs(i, j) {
    if (i < 0 || i >= y || j < 0 || j >= x || grid[i][j] !== "1") return;
    // Mark the cell as visited
    grid[i][j] = "0";
    dfs(i - 1, j);
    dfs(i, j + 1);
    dfs(i + 1, j);
    dfs(i, j - 1);
  }
  // Main loop to iterate through the grid
  for (let i = 0; i < grid.length; i++) {
    for (let j = 0; j < grid[i].length; j++) {
      if (grid[i][j] === "1") {
        count++;
        dfs(i, j);
      }
    }
  }
  return count;
};

const grid = [
  ["1", "1", "0", "0", "0"],
  ["1", "1", "0", "0", "0"],
  ["0", "0", "1", "0", "0"],
  ["0", "0", "0", "1", "1"],
];

console.log(numIslands(grid));

Dealing with .DS_Store Files on macOS: Keeping Your Git Development Clean

benono — Tue, 10 Sep 2024 16:41:59 +0000

When developing with Git on macOS, you may find .DS_Store files unintentionally added to your repository. These files are specific to macOS and unnecessary for your project. This article introduces effective methods to solve this issue.

What is .DS_Store?

.DS_Store (Desktop Services Store) files are hidden files used by macOS Finder to store folder display settings. These are unnecessary for project version control and can be noise for users of other operating systems.

Solution Steps

1. Create a Global .gitignore File

First, let's set up a global configuration that applies to all Git projects.

cd ~
echo .DS_Store >> .gitignore_global
git config --global core.excludesfile ~/.gitignore_global

This creates a .gitignore_global file in your home directory and applies it to Git's global configuration.

2. Update Project-Specific .gitignore File

Next, configure individual projects to ignore .DS_Store files. Add the following to your project's .gitignore file:

# macOS
.DS_Store

3. Remove Already Tracked .DS_Store Files

If .DS_Store files have already been added to your repository, you can remove them with the following commands:

find . -name .DS_Store -print0 | xargs -0 git rm --ignore-unmatch
git commit -m "Remove .DS_Store files"

Conclusion

By implementing these steps, you can effectively prevent .DS_Store files from being included in your project's version control. This setup allows macOS users to work in a cleaner Git environment and facilitates smoother collaboration with team members using other operating systems.

DEV Community: benono