🚀 Code Challengers

Master algorithmic challenges with our AI-powered platform

K-Diverse Partition

Hard

📋 Problem Description

Given an array of integers and a value k, partition the array into subarrays such that each subarray contains at most k distinct elements. The goal is to minimize the number of partitions while ensuring no partition exceeds k distinct elements. A k-diverse partition is valid if: 1. Each partition contains at most k distinct elements 2. The array is completely partitioned (no elements left out) 3. Partitions maintain the original order of elements Return the minimum number of partitions needed.

💡 Examples

Example 1
Input: arr = [1,2,1,2,3], k = 2
Output: 2
Explanation: Optimal partitioning: [1,2,1,2] (2 distinct: 1,2) and [3] (1 distinct: 3). Total: 2 partitions.
Example 2
Input: arr = [1,2,3,4], k = 2
Output: 2
Explanation: Optimal partitioning: [1,2] (2 distinct) and [3,4] (2 distinct). Total: 2 partitions.
Example 3
Input: arr = [1,1,1,1], k = 3
Output: 1
Explanation: All elements are the same, so [1,1,1,1] has only 1 distinct element ≤ 3. Total: 1 partition.

⚡ Constraints

  • 1 ≤ n ≤ 10⁵ (where n is the length of the array)
  • 1 ≤ k ≤ n
  • 1 ≤ arr[i] ≤ 10⁶
  • Time complexity should be O(n) or O(n log n)
  • Space complexity should be O(k) or better
14px
💡 Press Ctrl + Enter to run code