Join Us
Loading Similar Posts
Entering edit mode
Question 1: Samurai & his Friends
Problem Statement: Samurai has a grid of chocolates with dimensions m x n. Positioned at the top-left corner (0, 0) is Samurai's friend Charlie, and at the top-right corner (0, n - 1) is his other friend Jack.
Both friends can move downward, collecting chocolates from the cells they pass through. When a friend passes through a cell, all chocolates in that cell are picked, reducing the count to zero.
Charlie and Jack, when at coordinates (i, j), have the option to move to one of three adjacent cells in the row below:
- Move directly down to (i + 1, j).
- Move diagonally down-left to (i + 1, j - 1).
- Move diagonally down-right to (i + 1, j + 1).
They must stay inside the grid while moving. If both friends end up in the same cell, only one of them gets the chocolates.
Your task is to determine the maximum number of chocolates Samurai can collect with the help of Charlie and Jack, following these rules.
Example 1: Input:
m = 3, n = 3
grid = [[10, 20, 10],
[30, 20, 10]...
(Array continues based on standard matrix inputs)
Question 2: Number Of Distinct Islands
Problem Statement: You are given a grid of dimension m by n of integers consisting of 0's and 1's. 1 represents land and 0 represents water.
Your task is to find the number of distinct islands where a group of connected 1s (horizontally or vertically) forms an island.
Note:
- Two islands are considered to be the same if and only if one island is equal to another (not rotated or reflected).
- In simpler terms, if we can translate one island onto another without rotating or reflecting it, then they would be considered the same islands.
Example 1: Input:
m (rows) = 3, n (columns) = 3,
grid = { { 1, 0, 0 },
{ 1, 0, 1 },
{ 0, 0, 1 } }
Entering edit mode
Problem 1 Solution:
Samurai & his Friends (Maximum Chocolates)
Topics Involved / Prerequisites
- Dynamic Programming (3D State)
- Grid Traversal
Overview
Because both friends move downward one row at a time simultaneously, they will always be on the same row. This synchronous movement allows us to define our state based on the current row and their respective column positions. We can use dynamic programming to explore all 9 possible combined moves (3 moves for Charlie * 3 moves for Jack) at each step, memoizing the results to avoid redundant calculations.
Approach
1. State Representation
Let dp(row, col1, col2) represent the maximum chocolates collected from the current row to the bottom of the grid, where Charlie is at col1 and Jack is at col2.
2. State Transitions
At any (row, col1, col2):
- Base Cases: If either friend goes out of the grid boundaries, return a highly negative number to invalidate that path. If they reach the end of the grid (row == m), return 0.
- Current Chocolates: If col1 == col2, they are in the same cell, so the chocolates are only counted once: grid[row][col1]. If they are in different cells, we add both: grid[row][col1] + grid[row][col2].
- Future Chocolates: We recursively call the DP function for the next row (row + 1) for all 9 possible column combinations (col1 - 1, col1, col1 + 1) and (col2 - 1, col2, col2 + 1). We find the maximum among these 9 paths and add it to our current chocolates.
Code Implementation (C++)
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int solve(int i, int j1, int j2, int m, int n, const vector<vector<int>>& grid, vector<vector<vector<int>>>& memo) {
// Base case: Out of bounds
if (j1 < 0 || j1 >= n || j2 < 0 || j2 >= n) {
return -1e9;
}
// Base case: Reached the last row
if (i == m - 1) {
if (j1 == j2) return grid[i][j1];
else return grid[i][j1] + grid[i][j2];
}
// Return memoized result if already computed
if (memo[i][j1][j2] != -1) {
return memo[i][j1][j2];
}
int maxChocolates = -1e9;
// Explore all 9 possible moves for the next row
for (int dj1 = -1; dj1 <= 1; dj1++) {
for (int dj2 = -1; dj2 <= 1; dj2++) {
int currentChocolates;
if (j1 == j2) {
currentChocolates = grid[i][j1];
} else {
currentChocolates = grid[i][j1] + grid[i][j2];
}
currentChocolates += solve(i + 1, j1 + dj1, j2 + dj2, m, n, grid, memo);
maxChocolates = max(maxChocolates, currentChocolates);
}
}
return memo[i][j1][j2] = maxChocolates;
}
int maximumChocolates(int m, int n, vector<vector<int>>& grid) {
// Initialize a 3D memoization table with -1
vector<vector<vector<int>>> memo(m, vector<vector<int>>(n, vector<int>(n, -1)));
return solve(0, 0, n - 1, m, n, grid, memo);
}
Time and Space Complexity
- Time Complexity: O(M * N^2) — Where M is the number of rows and N is the number of columns. We calculate the answer for M * N * N unique states, and each state takes O(1) time (evaluating 9 transitions).
- Space Complexity: O(M * N^2) — For the 3D memoization table and the recursive call stack.
Entering edit mode
Problem 2 Solution:
Number Of Distinct Islands
Topics Involved / Prerequisites
- Depth First Search (DFS) / Breadth First Search (BFS)
- Hash Sets
- Coordinate Geometry (Relative Positioning)
Overview
To count the number of distinct islands, we need a way to represent the "shape" of an island independently of its absolute position on the grid. We can do this by recording the coordinates of all cells in an island relative to the starting cell of that island. If two islands have the same set of relative coordinates, they are identical in shape.
Approach
1. Island Traversal
We iterate through the grid. Whenever we find unvisited land (1), it marks the start of a new island. We trigger a DFS or BFS from this cell to find all connected 1s.
2. Capturing the Shape
Let the starting cell of our DFS be (r_0, c_0). For every cell (r, c) we visit in this specific island, we compute its relative position as (r - r_0, c - c_0). We store these relative coordinates in a list.
3. Uniqueness Check
Once the DFS for an island is complete, we insert the list of its relative coordinates into a std::set. Because sets automatically discard duplicates, identical shapes will overwrite each other. The final answer is simply the size of the set.
Code (C++)
#include <iostream>
#include <vector>
#include <set>
using namespace std;
void dfs(int row, int col, int m, int n, const vector<vector<int>>& grid,
vector<vector<bool>>& visited, vector<pair<int, int>>& shape, int row0, int col0) {
visited[row][col] = true;
// Store the relative coordinates
shape.push_back({row - row0, col - col0});
// Define the 4 directional moves: Up, Right, Down, Left
int delRow[] = {-1, 0, 1, 0};
int delCol[] = {0, 1, 0, -1};
for (int i = 0; i < 4; i++) {
int nRow = row + delRow[i];
int nCol = col + delCol[i];
// Check boundaries and if the cell is unvisited land
if (nRow >= 0 && nRow < m && nCol >= 0 && nCol < n &&
!visited[nRow][nCol] && grid[nRow][nCol] == 1) {
dfs(nRow, nCol, m, n, grid, visited, shape, row0, col0);
}
}
}
int countDistinctIslands(int m, int n, vector<vector<int>>& grid) {
vector<vector<bool>> visited(m, vector<bool>(n, false));
set<vector<pair<int, int>>> uniqueIslands;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (!visited[i][j] && grid[i][j] == 1) {
vector<pair<int, int>> shape;
// Pass the starting coordinates (i, j) as the base (row0, col0)
dfs(i, j, m, n, grid, visited, shape, i, j);
uniqueIslands.insert(shape);
}
}
}
return uniqueIslands.size();
}
Time and Space Complexity
- Time Complexity: O(M * N * log(K)) — Where M * N is the grid size and K is the number of distinct islands. We visit each cell exactly once. Inserting a vector of coordinates into a set takes logarithmic time relative to the number of unique shapes.
- Space Complexity: O(M * N) — For the visited matrix and the space required to store the coordinate vectors in the set.
