Welcome to Subscribe On Youtube

3254. Find the Power of K-Size Subarrays I

Description

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 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] <= 105
• 1 <= k <= n

Solutions

Solution 1: Recursion

We define an array $f$, where $f[i]$ represents the length of the continuous increasing subsequence ending at the $i$-th element. Initially, $f[i] = 1$.

Next, we traverse the array $\textit{nums}$ to calculate the values of the array $f$. If $nums[i] = nums[i - 1] + 1$, then $f[i] = f[i - 1] + 1$; otherwise, $f[i] = 1$.

Then, we traverse the array $f$ in the range $[k - 1, n)$. If $f[i] \ge k$, we add $\textit{nums}[i]$ to the answer array; otherwise, we add $-1$.

After the traversal, we return the answer array.

The time complexity is $O(n)$, and the space complexity is $O(n)$. Here, $n$ represents the length of the array $\textit{nums}$.

Solution 2

This implementation follows the required operations directly. It traverses the relevant values and updates its state as each value is processed. After all required states have been considered, the maintained result is returned.

• Java
• C++
• Python
• Go
• TypeScript
• Javascript

• class Solution {
      public int[] resultsArray(int[] nums, int k) {
          int n = nums.length;
          int[] f = new int[n];
          Arrays.fill(f, 1);
          for (int i = 1; i < n; ++i) {
              if (nums[i] == nums[i - 1] + 1) {
                  f[i] = f[i - 1] + 1;
              }
          }
          int[] ans = new int[n - k + 1];
          for (int i = k - 1; i < n; ++i) {
              ans[i - k + 1] = f[i] >= k ? nums[i] : -1;
          }
          return ans;
      }
  }
  
  

• class Solution {
  public:
      vector<int> resultsArray(vector<int>& nums, int k) {
          int n = nums.size();
          int f[n];
          f[0] = 1;
          for (int i = 1; i < n; ++i) {
              f[i] = nums[i] == nums[i - 1] + 1 ? f[i - 1] + 1 : 1;
          }
          vector<int> ans;
          for (int i = k - 1; i < n; ++i) {
              ans.push_back(f[i] >= k ? nums[i] : -1);
          }
          return ans;
      }
  };
  
  

• class Solution:
      def resultsArray(self, nums: List[int], k: int) -> List[int]:
          n = len(nums)
          f = [1] * n
          for i in range(1, n):
              if nums[i] == nums[i - 1] + 1:
                  f[i] = f[i - 1] + 1
          return [nums[i] if f[i] >= k else -1 for i in range(k - 1, n)]
  
  

• func resultsArray(nums []int, k int) (ans []int) {
  	n := len(nums)
  	f := make([]int, n)
  	f[0] = 1
  	for i := 1; i < n; i++ {
  		if nums[i] == nums[i-1]+1 {
  			f[i] = f[i-1] + 1
  		} else {
  			f[i] = 1
  		}
  	}
  	for i := k - 1; i < n; i++ {
  		if f[i] >= k {
  			ans = append(ans, nums[i])
  		} else {
  			ans = append(ans, -1)
  		}
  	}
  	return
  }
  
  

• function resultsArray(nums: number[], k: number): number[] {
      const n = nums.length;
      const f: number[] = Array(n).fill(1);
      for (let i = 1; i < n; ++i) {
          if (nums[i] === nums[i - 1] + 1) {
              f[i] = f[i - 1] + 1;
          }
      }
      const ans: number[] = [];
      for (let i = k - 1; i < n; ++i) {
          ans.push(f[i] >= k ? nums[i] : -1);
      }
      return ans;
  }
  
  
  // Solution 2
  export function resultsArray(nums: number[], k: number): number[] {
      const n = nums.length;
      const ans: number[] = [];
  
      for (let i = 0, j = 0; i < n; i++) {
          if (i && nums[i - 1] + 1 !== nums[i]) j = i;
          if (i >= k - 1) {
              ans.push(i - k + 1 < j ? -1 : nums[i]);
          }
      }
  
      return ans;
  }
  
  

• // Solution 2
  export function resultsArray(nums, k) {
      const n = nums.length;
      const ans = [];
  
      for (let i = 0, j = 0; i < n; i++) {
          if (i && nums[i - 1] + 1 !== nums[i]) j = i;
          if (i >= k - 1) {
              ans.push(i - k + 1 < j ? -1 : nums[i]);
          }
      }
  
      return ans;
  }
  
  

All Problems

All Solutions