algoadvance

Leetcode 2951. Find the Peaks

Problem Statement

You are given an integer array nums. A peak element in this array is an element that is greater than its neighbors. For example, in the array [1, 3, 2], 3 is a peak element since it’s greater than both 1 (its left neighbor) and 2 (its right neighbor). You need to write a function findPeaksOut that returns a list of all the peak elements in the array.

The function signature is:

List<Integer> findPeaksOut(int[] nums)

Clarifying Questions

1. What should be the behavior at the boundaries of the array?
   • Consider the array nums: If nums[i] (where i is the index) is at the boundary (i.e., i == 0 or i == nums.length - 1), it’s a peak if it is greater than its single neighbor.
2. What if the array has duplicate elements?
   • A peak is defined strictly; hence duplicates won’t be considered as functional peaks unless the element is strictly greater than adjacent elements.
3. What should the output be if there are no peak elements?
   • The function should return an empty list.

Strategy

1. Initialize an empty list to store the peak elements.
2. Iterate through the array:
   • For each element, compare it with its neighbors.
   • Add the element to the list if it satisfies the peak condition.
3. Consider edge cases:
   • Single-element array.
   • Arrays where no element qualifies as a peak (e.g., all elements are the same).

Code

import java.util.*;

public class FindPeaks {
    public static List<Integer> findPeaksOut(int[] nums) {
        List<Integer> peaks = new ArrayList<>();
        
        if (nums == null || nums.length == 0) {
            return peaks;
        }
        
        int n = nums.length;
        
        for (int i = 0; i < n; i++) {
            // Check if the current element is a peak
            boolean isPeak = false;
            
            if (i == 0) {
                // First element peak condition (greater than next element)
                if (n == 1 || nums[i] > nums[i + 1]) {
                    isPeak = true;
                }
            } else if (i == n - 1) {
                // Last element peak condition (greater than previous element)
                if (nums[i] > nums[i - 1]) {
                    isPeak = true;
                }
            } else {
                // Middle elements peak condition (greater than both neighbors)
                if (nums[i] > nums[i - 1] && nums[i] > nums[i + 1]) {
                    isPeak = true;
                }
            }
            
            if (isPeak) {
                peaks.add(nums[i]);
            }
        }
        
        return peaks;
    }

    public static void main(String[] args) {
        int[] nums1 = {1, 3, 2, 4, 1};
        int[] nums2 = {1, 2, 3, 4, 5};
        int[] nums3 = {5, 4, 3, 2, 1};
        int[] nums4 = {2, 2, 2, 2};

        System.out.println(findPeaksOut(nums1)); // Output: [3, 4]
        System.out.println(findPeaksOut(nums2)); // Output: [5]
        System.out.println(findPeaksOut(nums3)); // Output: [5]
        System.out.println(findPeaksOut(nums4)); // Output: []
    }
}

Time Complexity

• The time complexity of this solution is O(n), where n is the number of elements in the array. This is because we are iterating through the array once to check each element.
• The space complexity is O(1) for the additional variables and O(k) for the output list, where k is the number of peak elements found.

This algorithm efficiently finds all the peak elements within a single pass through the array.

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?