Medium
You are given an integer array nums
and an integer k
.
The frequency of an element x
is the number of times it occurs in an array.
An array is called good if the frequency of each element in this array is less than or equal to k
.
Return the length of the longest good subarray of nums
.
A subarray is a contiguous non-empty sequence of elements within an array.
Example 1:
Input: nums = [1,2,3,1,2,3,1,2], k = 2
Output: 6
Explanation: The longest possible good subarray is [1,2,3,1,2,3] since the values 1, 2, and 3 occur at most twice in this subarray. Note that the subarrays [2,3,1,2,3,1] and [3,1,2,3,1,2] are also good. It can be shown that there are no good subarrays with length more than 6.
Example 2:
Input: nums = [1,2,1,2,1,2,1,2], k = 1
Output: 2
Explanation: The longest possible good subarray is [1,2] since the values 1 and 2 occur at most once in this subarray. Note that the subarray [2,1] is also good. It can be shown that there are no good subarrays with length more than 2.
Example 3:
Input: nums = [5,5,5,5,5,5,5], k = 4
Output: 4
Explanation: The longest possible good subarray is [5,5,5,5] since the value 5 occurs 4 times in this subarray. It can be shown that there are no good subarrays with length more than 4.
Constraints:
1 <= nums.length <= 105
1 <= nums[i] <= 109
1 <= k <= nums.length
import kotlin.math.max
import kotlin.math.min
class Solution {
fun maxSubarrayLength(nums: IntArray, k: Int): Int {
var m1 = Int.MIN_VALUE
var m2 = Int.MAX_VALUE
for (num in nums) {
m1 = max(m1.toDouble(), num.toDouble()).toInt()
m2 = min(m2.toDouble(), num.toDouble()).toInt()
}
var max = 0
val f = IntArray(m1 - m2 + 1)
var l = 0
var r = 0
while (r < nums.size) {
f[nums[r] - m2]++
while (count(f, nums[r] - m2) > k) {
f[nums[l] - m2]--
l++
}
max = max(max.toDouble(), (r - l + 1).toDouble()).toInt()
r++
}
return max
}
private fun count(f: IntArray, n: Int): Int {
return f[n]
}
}