3_leetcode_patterns.md

Combined Lesson - 3 Leetcode Patterns

Section 1

LeetCode Practice Patterns - Day 46: Shortest Paths - Bellman-Ford and Floyd-Warshall

This lesson maps directly to patterns required to solve LeetCode problems.

Key Patterns

• Analyze constraints to choose the optimal time/space boundaries.
• Beware of common traps like index errors, infinite loops, and boundary overflows.

Recommended LeetCode Questions

🔴 LC 787: Cheapest Flights Within K Stops

• Difficulty: Medium
• Solving Strategy: Use Bellman-Ford algorithm relaxed exactly K+1 times, or use modified Dijkstra tracking stop limits.

🔴 LC 1334: Find the City With the Smallest Number of Neighbors at a Threshold Distance

• Difficulty: Medium
• Solving Strategy: Run Floyd-Warshall to compute all-pairs shortest path matrix, then count destinations within the threshold distance.

---

Next Steps

• Write down your own solutions in a file (e.g. solution.py) inside this folder.
• Execute your code locally and submit on LeetCode to verify.

 ◀ Prev                    Next ▶ 

Section 2

LeetCode Practice Patterns - Day 46: Shortest Path - Bellman-Ford and Floyd-Warshall

This guide details bounded edge relaxations and all-pairs distance matrices patterns for solving LeetCode problems.

---

📅 Recommended LeetCode Questions

🟠 LC 787: Cheapest Flights Within K Stops

• Difficulty: Medium
• Concept: Bounded Bellman-Ford / DP Edge Relaxations ($O(K \cdot E)$ Time | $O(V)$ Space).
• The Pattern: A path with at most $K$ stops can contain at most $K+1$ edge connections. Perform $K+1$ relaxation iterations on the flights list. To ensure that an update made in the current pass does not propagate along multiple edges in that same pass, make a copy of the distances array temp = dist[:] at the start of each iteration.

  def findCheapestPrice(n: int, flights: list[list[int]], src: int, dst: int, k: int) -> int:
      dist = [float('inf')] * n
      dist[src] = 0
      
      for _ in range(k + 1):
          temp = dist[:]
          for u, v, w in flights:
              if dist[u] != float('inf') and dist[u] + w < temp[v]:
                  temp[v] = dist[u] + w
          dist = temp
          
      return dist[dst] if dist[dst] != float('inf') else -1

---

🟠 LC 1334: Find the City With the Smallest Number of Neighbors at a Threshold Distance

• Difficulty: Medium
• Concept: Floyd-Warshall All-Pairs Distance Matrix ($O(V^3)$ Time | $O(V^2)$ Space).
• The Pattern:
  1. Build a $V \times V$ distance matrix. Initialize with infinity, and diagonal entries matrix[i][i] = 0.
  2. Populate with edges weights.
  3. Run Floyd-Warshall (3-nested loops) to calculate all-pairs shortest paths.
  4. For each city, count how many other cities are reachable within the distanceThreshold. Return the city with the smallest count (resolving ties by returning the city with the largest index).

  def findTheCity(n: int, edges: list[list[int]], distanceThreshold: int) -> int:
      # Initialize matrix
      dist = [[float('inf')] * n for _ in range(n)]
      for i in range(n):
          dist[i][i] = 0
          
      for u, v, w in edges:
          dist[u][v] = w
          dist[v][u] = w
          
      # Floyd-Warshall
      for k in range(n):
          for i in range(n):
              for j in range(n):
                  dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
                  
      # Count reachable neighbors within threshold
      min_count = float('inf')
      ans_city = -1
      
      for i in range(n):
          count = sum(1 for j in range(n) if dist[i][j] <= distanceThreshold)
          # We only compare against '<=' to ensure larger city indexes override ties
          if count <= min_count:
              min_count = count
              ans_city = i
              
      return ans_city

 ◀ Prev                    Next ▶