algoadvance

Leetcode 2951. Find the Peaks

Problem Statement

You are given a 2D grid grid of size n x m with the following conditions:

• grid[i][j] is an integer representing the height at cell (i, j).

A peak in the grid is an element that is greater than its 4 neighboring cells (top, bottom, left, and right). We need to find and return a list of all peak elements in the grid.

Clarifying Questions

1. Boundaries: How should we treat the boundaries of the grid?
   • The elements on the boundaries should be compared only to their existing neighbors. For example, if an element is on the top row, it would only be compared to the elements directly below it, and to its left or right.
2. Dimensions: What are the constraints on the grid dimensions n and m?
   • Assume n and m are both at least 1.
3. Duplicates: Can multiple peak elements have the same value?
   • Yes, elements with the same value can still be considered peaks as long as they satisfy the peak condition relative to their neighbors.

Strategy

1. Traversal: We’ll traverse each cell in the grid.
2. Conditions Check:
   • For each cell (i, j), we compare it with its neighbors (i-1, j), (i+1, j), (i, j-1), and (i, j+1) if they exist.
   • If the current cell is strictly greater than all its available neighbors, it is considered a peak.
3. Boundary Handling: Special care must be taken to only compare existing neighbors.
4. Result Collection: Collect all peak elements in a list and return it.

Time Complexity

• Time Complexity: O(n * m) since we traverse each element exactly once and perform a constant amount of work for each.
• Space Complexity: O(k) for the result list, where k is the number of peak elements.

Code

#include <vector>

std::vector<int> findPeaks(std::vector<std::vector<int>>& grid) {
    if (grid.empty()) return {};
    
    int n = grid.size();
    int m = grid[0].size();
    std::vector<int> peaks;

    // Directions for traversing: up, down, left, right
    std::vector<std::pair<int, int>> directions = \{\{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            bool isPeak = true;
            for (const auto& dir : directions) {
                int ni = i + dir.first;
                int nj = j + dir.second;
                // Check if neighbor is in the grid
                if (ni >= 0 && ni < n && nj >= 0 && nj < m) {
                    if (grid[i][j] <= grid[ni][nj]) {
                        isPeak = false;
                        break;
                    }
                }
            }
            if (isPeak) {
                peaks.push_back(grid[i][j]);
            }
        }
    }

    return peaks;
}

Explanation

1. Initialization: Initialize direction vectors to facilitate checking neighboring cells.
2. Nested Loops: Use nested loops to traverse every cell in the grid.
3. Peak Check: For each cell, check whether it is greater than all of its valid neighbors.
4. Collection: Add cells that are peaks to the peaks vector.
5. Return: Return the peaks vector containing all peak elements.

This code ensures that we handle boundary conditions appropriately and only compare existing neighboring elements.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?