3254. Find the Power of K-Size Subarrays I

Discussed in https://github.com/mah-shamim/leet-code-in-php/discussions/839

^{Originally posted by **mah-shamim** November 16, 2024} **Topics:** `Array`, `Sliding Window` You are given an array of integers `nums` of length `n` and a _positive_ integer `k`. The **power** of an array is defined as: - Its **maximum** element if all of its elements are **consecutive** and sorted in **ascending** order. - `-1` otherwise. You need to find the **power** of all subarrays[^1] of nums of size k. Return an integer array `results` of size `n - k + 1`, where `results[i]` is the _power_ of `nums[i..(i + k - 1)]`. **Example 1:** - **Input:** nums = [1,2,3,4,3,2,5], k = 3 - **Output:** [3,4,-1,-1,-1] - **Explanation:** There are 5 subarrays of `nums` of size 3: - `[1, 2, 3]` with the maximum element 3. - `[2, 3, 4]` with the maximum element 4. - `[3, 4, 3]` whose elements are **not** consecutive. - `[4, 3, 2]` whose elements are **not** sorted. - `[3, 2, 5]` whose elements are **not** consecutive. **Example 2:** - **Input:** nums = [2,2,2,2,2], k = 4 - **Output:** [-1,-1] **Example 3:** - **Input:** nums = [3,2,3,2,3,2], k = 2 - **Output:** [-1,3,-1,3,-1] **Constraints:** - `1 <= n == nums.length <= 500` - 1 <= nums[i] <= 10⁵ - `1 <= k <= n` **Hint:** 1. Can we use a brute force solution with nested loops and HashSet? [^1]: **Subarray**: A subarray is a contiguous non-empty sequence of elements within an array.

We can break down the task as follows:

Problem Breakdown:

We are given an array nums of length n, and a positive integer k. We need to consider all subarrays of size k and compute their power.
The power of a subarray is:
- The maximum element of the subarray if all the elements are consecutive and sorted in ascending order.
- -1 otherwise.
We need to return an array of size n - k + 1, where each element corresponds to the power of the respective subarray.

Plan:

Sliding Window Approach: We will slide over the array and check each subarray of length k.
Check if the Subarray is Sorted: We need to check if the subarray has elements that are consecutive and sorted in ascending order.
Return Maximum or -1: If the subarray is valid, we return the maximum element. Otherwise, return -1.

Steps:

Check if the subarray is sorted:
- A sorted subarray with consecutive elements should have the property: nums[i+1] - nums[i] == 1 for every i in the subarray.
Sliding Window:
- For each subarray of length k, check if it is sorted and return the maximum element if valid, otherwise return -1.

Let's implement this solution in PHP: 3254. Find the Power of K-Size Subarrays I

<?php
/**
 * @param Integer[] $nums
 * @param Integer $k
 * @return Integer[]
 */
function resultsArray($nums, $k) {
    $n = count($nums);
    $result = [];

    // Iterate through all subarrays of size k
    for ($i = 0; $i <= $n - $k; $i++) {
        $subarray = array_slice($nums, $i, $k);
        $isSorted = true;

        // Check if the subarray is sorted with consecutive elements
        for ($j = 0; $j < $k - 1; $j++) {
            if ($subarray[$j] + 1 !== $subarray[$j + 1]) {
                $isSorted = false;
                break;
            }
        }

        // If sorted and consecutive, return the maximum, else -1
        if ($isSorted) {
            $result[] = max($subarray);
        } else {
            $result[] = -1;
        }
    }

    return $result;
}

// Test cases
print_r(resultsArray([1, 2, 3, 4, 3, 2, 5], 3));  // Output: [3, 4, -1, -1, -1]
print_r(resultsArray([2, 2, 2, 2, 2], 4));  // Output: [-1, -1]
print_r(resultsArray([3, 2, 3, 2, 3, 2], 2));  // Output: [-1, 3, -1, 3, -1]
?>

Explanation:

Sliding Window: We use a for loop from i = 0 to i = n - k to consider all subarrays of size k. For each subarray, we use array_slice() to extract the subarray.
Sorting Check: For each subarray, we check if it is sorted with consecutive elements by iterating through the subarray and checking if each pair of consecutive elements has a difference of 1.
Result: If the subarray is valid, we append the maximum value of the subarray to the result. Otherwise, we append -1.

Time Complexity:

We are iterating over n - k + 1 subarrays.
For each subarray, we check if the elements are consecutive, which takes O(k) time.
Thus, the overall time complexity is O((n - k + 1) * k) which simplifies to O(n * k).

Edge Case Considerations:

If k = 1, every subarray is trivially sorted (it only contains one element), and the power of each subarray will be the element itself.
If the subarray is not consecutive, it will immediately return -1.

Example Outputs:

For nums = [1, 2, 3, 4, 3, 2, 5], k = 3, the output is [3, 4, -1, -1, -1].
For nums = [2, 2, 2, 2, 2], k = 4, the output is [-1, -1].
For nums = [3, 2, 3, 2, 3, 2], k = 2, the output is [-1, 3, -1, 3, -1].

This solution should efficiently work for the problem constraints.

mah-shamim / leet-code-in-php