Number of Ships in Harbor

You're about to set sail off a pier and first want to count the number of ships that are already in the harbor. The harbor is deemed safe to sail in if the number of boats in the harbor is strictly less than limit. Given a 2D array that presents the harbor, where O represents water and S represents a ship, return whether or not it's safe for you to set sail.

Note: All ships in the harbor can only lie entirely vertically or entirely horizontally and cannot be connected to another ship.

Example(s)

Example 1:

Input: harbor = [
    ['O', 'O', 'S'],
    ['S', 'O', 'O'],
    ['O', 'O', 'S']
], limit = 5

Output: true
Explanation:
There are 3 ships in the harbor:
- Ship 1 at position (0,2)
- Ship 2 at position (1,0)
- Ship 3 at position (2,2)
After you set sail, there will be 4 ships (3 + 1 = 4).
4 < 5, so it's safe to sail.

Example 2:

Input: harbor = [
    ['O', 'O', 'O'],
    ['S', 'O', 'S'],
    ['O', 'O', 'S']
], limit = 3

Output: false
Explanation:
There are 2 ships in the harbor:
- Ship 1 at position (1,0)
- Ship 2 at positions (1,2) and (2,2) (connected horizontally/vertically)
After you set sail, there will be 3 ships (2 + 1 = 3).
3 is NOT strictly less than 3, so it's not safe to sail.

Example 3:

Input: harbor = [
    ['S', 'S', 'O'],
    ['O', 'O', 'O'],
    ['O', 'O', 'S']
], limit = 2

Output: false
Explanation:
There are 2 ships:
- Ship 1 at positions (0,0) and (0,1) (horizontal)
- Ship 2 at position (2,2)
After you set sail: 2 + 1 = 3, which is NOT < 2.

Solution

The solution uses DFS/BFS to count ships:

1. Count ships: Use DFS/BFS to find all connected components of 'S'
2. Connected components: Ships are connected horizontally or vertically (not diagonally)
3. Add your ship: Count existing ships + 1 (your ship)
4. Check safety: Return true if (count + 1) < limit, false otherwise

JavaScript Solution

JavaScript Solution - DFS

/**
* Check if harbor is safe to sail
* @param {string[][]} harbor - 2D array (O = water, S = ship)
* @param {number} limit - Maximum number of ships allowed
* @return {boolean} - True if safe to sail (current ships + 1 < limit)
*/
function isSafeToSail(harbor, limit) {
if (!harbor || harbor.length === 0) {
  return 1 < limit; // No ships, adding yours makes 1
}

const rows = harbor.length;
const cols = harbor[0].length;
const visited = Array(rows).fill().map(() => Array(cols).fill(false));
let shipCount = 0;

/**
 * DFS to mark all cells of a ship as visited
 * @param {number} row - Current row
 * @param {number} col - Current column
 */
function dfs(row, col) {
  if (
    row < 0 || row >= rows ||
    col < 0 || col >= cols ||
    visited[row][col] ||
    harbor[row][col] === 'O'
  ) {
    return;
  }
  
  visited[row][col] = true;
  
  // Explore horizontally and vertically (not diagonally)
  dfs(row - 1, col); // up
  dfs(row + 1, col); // down
  dfs(row, col - 1); // left
  dfs(row, col + 1); // right
}

// Count ships
for (let i = 0; i < rows; i++) {
  for (let j = 0; j < cols; j++) {
    if (harbor[i][j] === 'S' && !visited[i][j]) {
      // Found a new ship
      shipCount++;
      dfs(i, j); // Mark all cells of this ship as visited
    }
  }
}

// Check if safe: current ships + your ship (1) < limit
return (shipCount + 1) < limit;
}

// Test cases
const harbor1 = [
['O', 'O', 'S'],
['S', 'O', 'O'],
['O', 'O', 'S']
];
console.log('Example 1:', isSafeToSail(harbor1, 5)); // true

const harbor2 = [
['O', 'O', 'O'],
['S', 'O', 'S'],
['O', 'O', 'S']
];
console.log('Example 2:', isSafeToSail(harbor2, 3)); // false

const harbor3 = [
['S', 'S', 'O'],
['O', 'O', 'O'],
['O', 'O', 'S']
];
console.log('Example 3:', isSafeToSail(harbor3, 2)); // false

Output:

Click "Run Code" to execute the code and see the results.

Python Solution

Python Solution - DFS

from typing import List

def is_safe_to_sail(harbor: List[List[str]], limit: int) -> bool:
  """
  Check if harbor is safe to sail
  
  Args:
      harbor: 2D array (O = water, S = ship)
      limit: Maximum number of ships allowed
      
  Returns:
      bool: True if safe to sail (current ships + 1 < limit)
  """
  if not harbor or not harbor[0]:
      return 1 < limit  # No ships, adding yours makes 1
  
  rows = len(harbor)
  cols = len(harbor[0])
  visited = [[False] * cols for _ in range(rows)]
  ship_count = 0
  
  def dfs(row: int, col: int):
      """
      DFS to mark all cells of a ship as visited
      """
      if (
          row < 0 or row >= rows or
          col < 0 or col >= cols or
          visited[row][col] or
          harbor[row][col] == 'O'
      ):
          return
      
      visited[row][col] = True
      
      # Explore horizontally and vertically (not diagonally)
      dfs(row - 1, col)  # up
      dfs(row + 1, col)  # down
      dfs(row, col - 1)  # left
      dfs(row, col + 1)  # right
  
  # Count ships
  for i in range(rows):
      for j in range(cols):
          if harbor[i][j] == 'S' and not visited[i][j]:
              # Found a new ship
              ship_count += 1
              dfs(i, j)  # Mark all cells of this ship as visited
  
  # Check if safe: current ships + your ship (1) < limit
  return (ship_count + 1) < limit

# Test cases
harbor1 = [
  ['O', 'O', 'S'],
  ['S', 'O', 'O'],
  ['O', 'O', 'S']
]
print('Example 1:', is_safe_to_sail(harbor1, 5))  # True

harbor2 = [
  ['O', 'O', 'O'],
  ['S', 'O', 'S'],
  ['O', 'O', 'S']
]
print('Example 2:', is_safe_to_sail(harbor2, 3))  # False

harbor3 = [
  ['S', 'S', 'O'],
  ['O', 'O', 'O'],
  ['O', 'O', 'S']
]
print('Example 3:', is_safe_to_sail(harbor3, 2))  # False

Loading Python runtime...

Output:

Click "Run Code" to execute the code and see the results.

Alternative Solution (BFS)

Here's a BFS version:

JavaScript BFS

/**
 * BFS approach
 */
function isSafeToSailBFS(harbor, limit) {
  if (!harbor || harbor.length === 0) {
    return 1 < limit;
  }
  
  const rows = harbor.length;
  const cols = harbor[0].length;
  const visited = Array(rows).fill().map(() => Array(cols).fill(false));
  let shipCount = 0;
  const directions = [[-1, 0], [1, 0], [0, -1], [0, 1]];
  
  function bfs(startRow, startCol) {
    const queue = [[startRow, startCol]];
    visited[startRow][startCol] = true;
    
    while (queue.length > 0) {
      const [row, col] = queue.shift();
      
      for (const [dr, dc] of directions) {
        const newRow = row + dr;
        const newCol = col + dc;
        
        if (
          newRow >= 0 && newRow < rows &&
          newCol >= 0 && newCol < cols &&
          !visited[newRow][newCol] &&
          harbor[newRow][newCol] === 'S'
        ) {
          visited[newRow][newCol] = true;
          queue.push([newRow, newCol]);
        }
      }
    }
  }
  
  for (let i = 0; i < rows; i++) {
    for (let j = 0; j < cols; j++) {
      if (harbor[i][j] === 'S' && !visited[i][j]) {
        shipCount++;
        bfs(i, j);
      }
    }
  }
  
  return (shipCount + 1) < limit;
}

Python BFS

from collections import deque

def is_safe_to_sail_bfs(harbor: List[List[str]], limit: int) -> bool:
    """
    BFS approach
    """
    if not harbor or not harbor[0]:
        return 1 < limit
    
    rows = len(harbor)
    cols = len(harbor[0])
    visited = [[False] * cols for _ in range(rows)]
    ship_count = 0
    directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    
    def bfs(start_row: int, start_col: int):
        queue = deque([(start_row, start_col)])
        visited[start_row][start_col] = True
        
        while queue:
            row, col = queue.popleft()
            
            for dr, dc in directions:
                new_row = row + dr
                new_col = col + dc
                
                if (
                    0 <= new_row < rows and
                    0 <= new_col < cols and
                    not visited[new_row][new_col] and
                    harbor[new_row][new_col] == 'S'
                ):
                    visited[new_row][new_col] = True
                    queue.append((new_row, new_col))
    
    for i in range(rows):
        for j in range(cols):
            if harbor[i][j] == 'S' and not visited[i][j]:
                ship_count += 1
                bfs(i, j)
    
    return (ship_count + 1) < limit

Complexity

• Time Complexity: O(m × n) - Where m and n are the dimensions of the harbor. We visit each cell at most once.
• Space Complexity: O(m × n) - For the visited array. The recursion stack (DFS) or queue (BFS) also uses O(m × n) in the worst case.

Approach

The solution uses DFS/BFS to count connected components:

1. Count ships:

   • Traverse the harbor
   • When we find an unvisited 'S', it's a new ship
   • Use DFS/BFS to mark all connected 'S' cells as visited

2. Connection rules:

   • Ships are connected horizontally or vertically (not diagonally)
   • All 'S' cells connected to each other form one ship

3. Check safety:

   • Count existing ships
   • Add 1 for your ship
   • Return true if (count + 1) < limit

Key Insights

• Connected components: Ships are connected components of 'S' cells
• 4-directional: Only check up, down, left, right (not diagonals)
• DFS/BFS: Both work to find connected components
• Strictly less than: The condition is < limit, not ≤ limit
• Add your ship: Always add 1 to the count

Step-by-Step Example

Let's trace through Example 1: harbor = [['O','O','S'],['S','O','O'],['O','O','S']], limit = 5

Harbor:
  ['O', 'O', 'S']
  ['S', 'O', 'O']
  ['O', 'O', 'S']

Step 1: Count ships
  (0,0): 'O' → skip
  (0,1): 'O' → skip
  (0,2): 'S' → new ship!
    DFS from (0,2):
      Check neighbors: all 'O' or out of bounds
      Ship 1: single cell at (0,2)
    shipCount = 1
  
  (1,0): 'S' → new ship!
    DFS from (1,0):
      Check neighbors: all 'O' or out of bounds
      Ship 2: single cell at (1,0)
    shipCount = 2
  
  (1,1): 'O' → skip
  (1,2): 'O' → skip
  (2,0): 'O' → skip
  (2,1): 'O' → skip
  (2,2): 'S' → new ship!
    DFS from (2,2):
      Check neighbors: all 'O' or out of bounds
      Ship 3: single cell at (2,2)
    shipCount = 3

Step 2: Check safety
  shipCount = 3
  After adding your ship: 3 + 1 = 4
  4 < 5? Yes → return true

Result: true

Visual Representation

Example 1:
  O O S    → Ship 1
  S O O    → Ship 2
  O O S    → Ship 3
  
  Total: 3 ships
  After you sail: 3 + 1 = 4 < 5 ✓

Example 2:
  O O O
  S O S    → Ship 1 (at 1,0)
  O O S    → Ship 2 (at 1,2 and 2,2, connected vertically)
  
  Total: 2 ships
  After you sail: 2 + 1 = 3, NOT < 3 ✗

Edge Cases

• Empty harbor: No ships, adding yours makes 1
• No ships: Return true if 1 < limit
• All water: Same as no ships
• All ships: Count all connected components
• Single ship: Works correctly
• Large ships: Multi-cell ships counted as one

Important Notes

• Strictly less than: Condition is < limit, not ≤ limit
• 4-directional: Only horizontal/vertical connections (not diagonal)
• Connected ships: All connected 'S' cells form one ship
• Your ship counts: Always add 1 to the existing count
• DFS/BFS: Both work for finding connected components

Related Problems

• Number of Islands: Similar connected components problem
• Max Area of Island: Different but related
• Surrounded Regions: Different problem but uses similar DFS
• Walls and Gates: BFS problem

Takeaways

• Connected components can be found using DFS/BFS
• 4-directional means up, down, left, right (not diagonals)
• Count + 1 accounts for your ship
• Strictly less than is the safety condition
• O(m×n) time is optimal (must visit all cells)