DSA Problems
Practice your coding skills with these DSA problems
| Title | Description | Difficulty |
|---|---|---|
| Leftmost Column with at Least a One | You are given a binary matrix with rows sorted in non-decreasing order. Implement a function to return the index of the leftmost column with at least a 1 in it. If no such column exists, return -1. The matrix is only accessible via a BinaryMatrix interface with the following methods: - get(row, col): returns the value at that cell (0 or 1) - dimensions(): returns [rows, cols] | Medium |
| Alien Dictionary | There is a new alien language which uses the Latin alphabet. The order among letters is unknown to you. You receive a list of non-empty words from this language, **sorted lexicographically** according to alien rules. Derive a possible character order of the language. Return any valid ordering of characters in the alien language. If the ordering is invalid or cannot be determined, return an empty string. **Notes:** - You may assume all letters are lowercase. - If `a` is a prefix of `b`, then `a` must come before `b` in the input list. - If the order is invalid (e.g. contradicting rules), return `""`. - If multiple valid orders exist, return any. **Example 1:** Input: ["wrt","wrf","er","ett","rftt"] Output: "wertf" **Example 2:** Input: ["z","x"] Output: "zx" **Example 3:** Input: ["z","x","z"] Output: "" (invalid ordering) | Hard |
| Number of Islands II | You are given an empty 2D grid with `m` rows and `n` columns, initially filled with water (0). We may perform a sequence of positions to add land (set grid[r][c] = 1). After each addition, return the number of islands. An island is a group of adjacent land cells connected horizontally or vertically. **Example:** Input: ``` m = 3, n = 3, positions = [[0,0],[0,1],[1,2],[2,1]] ``` Output: `[1,1,2,3]` **Explanation:** After adding land at (0,0) -> 1 island (0,1) -> cells (0,0) and (0,1) connect -> 1 island (1,2) -> new isolated cell -> 2 islands (2,1) -> new isolated cell -> 3 islands | Hard |
| Design Hit Counter | Design a hit counter which counts the number of hits received in the past 5 minutes (the past 300 seconds). Your system should support: - `void hit(int timestamp)`: record a hit at given timestamp (in seconds granularity). - `int getHits(int timestamp)`: return the number of hits in the past 300 seconds (inclusive of current timestamp). Assume timestamps are non-decreasing when called. | Medium |
| Bomb Enemy | Given a 2D grid, each cell is `'W'` (wall), `'E'` (enemy), or `'0'` (empty), return the maximum number of enemies you can eliminate by placing a bomb in an empty cell. The bomb kills all enemies in the same row and column until a wall blocks it. **Example:** ``` Grid: [['0','E','0','0'], ['E','0','W','E'], ['0','E','0','0']] ``` Output: `3` (placing bomb at (1,1) kills 3 enemies) | Medium |