Problem of The Day: Find the Power of K-Size Subarrays I

Problem Statement

Intuition

The goal of the algorithm is to identify segments of the input list nums of size k where all elements form a continuous sequence. A continuous sequence is defined as a sequence of integers that start from a value x and increase by 1 consistently. For each valid segment, the last element of the sequence is added to the result. If the sequence is not valid, -1 is appended instead.

Approach

1. Sliding Window: To process the list efficiently, the algorithm uses a sliding window of size k. This allows checking all subarrays of size k in linear time relative to the size of the array.
2. Validation: Each subarray is validated using the isValid method. This method checks if the subarray forms a continuous sequence by iterating through its elements.
3. Building Results: If the current window is valid, the last element of the window is added to the result. Otherwise, -1 is appended.
4. Iteration: The window slides forward by incrementing the left (l) and right (r) pointers until the right pointer reaches the end of the array.

Complexity

• Time Complexity:

  • The outer loop runs \(O(N - k + 1)\) times, where \(N\) is the length of the array.
  • The isValid function iterates over each window of size k, making the total complexity \(O(N \cdot k)\).
  • Overall: \(O(N \cdot k)\).

• Space Complexity:

  • The algorithm uses a list res to store the results, which has a size proportional to \(O(N - k + 1)\).
  • Overall: \(O(N)\).

Code

class Solution:
    def resultsArray(self, nums: List[int], k: int) -> List[int]:
        l, r = 0, k
        N = len(nums)
        res = []
        while r <= N:
            if self.isValid(nums[l:r]):
                res.append(nums[r - 1])
            else:
                res.append(-1)
            l += 1
            r += 1
        return res

    def isValid(self, arr):
        curr = arr[0]
        for x in arr:
            if curr != x:
                return False
            curr += 1
        return True

Editorial

Approach 1: Brute Force

class Solution:
    def resultsArray(self, nums: List[int], k: int) -> List[int]:
        length = len(nums)
        result = [0] * (length - k + 1)

        for start in range(length - k + 1):
            is_consecutive_and_sorted = True

            # Check if the current subarray is sorted and consecutive
            for index in range(start, start + k - 1):
                if nums[index + 1] != nums[index] + 1:
                    is_consecutive_and_sorted = False
                    break

            # If valid, take the maximum of the subarray, otherwise set to -1
            if is_consecutive_and_sorted:
                # Maximum element of this subarray
                result[start] = nums[start + k - 1]
            else:
                result[start] = -1

        return result

• time: O(n * k)
• space: O(1)

Approach 2: Sliding Window with Deque

class Solution:
    def resultsArray(self, nums: List[int], k: int) -> List[int]:
        length = len(nums)
        result = [-1] * (length - k + 1)
        index_deque = collections.deque()

        for current_index in range(length):
            if index_deque and index_deque[0] < current_index - k + 1:
                index_deque.popleft()
            if (
                index_deque
                and nums[current_index] != nums[current_index - 1] + 1
            ):
                index_deque.clear()

            index_deque.append(current_index)

            if current_index >= k - 1:
                if len(index_deque) == k:
                    result[current_index - k + 1] = nums[index_deque[-1]]
                else:
                    result[current_index - k + 1] = -1

        return result

• time: O(n)
• space: O(k)

Approach 3: Optimized Via Counter

class Solution:
    def resultsArray(self, nums, k):
        if k == 1:
            return nums  # If k is 1, every single element is a valid subarray

        length = len(nums)
        result = [-1] * (length - k + 1)
        consecutive_count = 1  # Count of consecutive elements

        for index in range(length - 1):
            if nums[index] + 1 == nums[index + 1]:
                consecutive_count += 1
            else:
                consecutive_count = 1  # Reset count if not consecutive

            # If we have enough consecutive elements, update the result
            if consecutive_count >= k:
                result[index - k + 2] = nums[index + 1]

        return result

• time: O(n)
• space: O(1)