import Mathlib /-! # Top K Frequent Elements Given an integer array nums and an integer k, return the k most frequent elements. You may return the answer in any order. ## Constraints - 1 <= nums.length <= 10^5 - -10^4 <= nums[i] <= 10^4 - k is in the range [1, the number of unique elements in the array]. - It is guaranteed that the answer is unique. ## Provided examples - `nums = [1, 1, 1, 2, 2, 3], k = 2` → `[1, 2]` - `nums = [1], k = 1` → `[1]` - `nums = [1, 2], k = 2` → `[1, 2]` ## Synthesized negative examples - invalid input: `nums = [10001], k = 1` ([structural] a predicate that admits -10^4 <= nums[i] <= 10^4. one past the stated maximum element value) - invalid input: `nums = [1, 1, 2, 2], k = 1` ([structural] a predicate that admits It is guaranteed that the answer is unique.. tie at the k-th frequency makes the answer non-unique) - invalid input: `nums = [1, 2], k = 0` ([structural] a predicate that admits k is in the range [1, the number of unique elements in the array].. one below the lower bound on k) - `nums = [1, 1, 1, 2, 2, 3], k = 2` → `[1, 3]` is wrong ([structural] optimality omitted; any achieved sum accepted. frequency sum 4, less than optimal 5) - `nums = [1], k = 1` → `[1, 1]` is wrong ([structural] no requirement that the output contain exactly k distinct elements. two copies of the sole element for k=1) - `nums = [1, 2], k = 2` → `[1]` is wrong ([structural] does not require the output to have exactly k elements. length is one less than k) -/ namespace PTopKFrequentElements abbrev Input := (List Int) × (Nat) abbrev Output := List Int /-! ### Specification helpers -/ /-- The number of occurrences of `x` in `nums`. -/ def Freq (nums : List Int) (x : Int) : Nat := nums.count x /-! ### Validity predicate (V) -/ /-- Valid input: 1 ≤ nums.length ≤ 10^5, every element in [-10^4, 10^4], k between 1 and the number of unique elements, and a qualifying set of the k most frequent elements exists (the strict separation makes it unique). -/ def isValidInput (input : Input) : Bool := let nums := input.1 let k := input.2 let u := nums.eraseDups.toFinset 1 ≤ nums.length && nums.length ≤ 100000 && nums.all (fun x => -10000 ≤ x && x ≤ 10000) && 1 ≤ k && k ≤ u.card && 0 < ((u.powersetCard k).filter fun S => (S.filter fun x => 0 < ((u \ S).filter fun y => Freq nums x ≤ Freq nums y).card).card = 0).card /-! ### Ideal specification (P_spec) -/ /-- `result` is a correct answer: there is a set `S` of exactly `k` integers such that `result` holds precisely the elements of `S`, each once, every element of `S` occurs in `nums`, and every element of `S` occurs strictly more often in `nums` than any element of `nums` outside `S`. -/ def topKFrequent_spec (input : Input) (result : Output) : Prop := ∃ S : Finset Int, (S.card = input.2 ∧ result.Nodup ∧ result.toFinset = S) ∧ (∀ x ∈ S, x ∈ input.1) ∧ ∀ x ∈ S, ∀ y ∈ input.1, y ∉ S → Freq input.1 x > Freq input.1 y /-! ### Decidable specification (P_check) -/ /-- Decides the existential over `Finset Int` by reducing it to the unique candidate `List.toFinset result`: the residual goal quantifies only over the lists `result` and `input.1`, which Lean decides on its own. -/ instance decTopKFrequentSpec (input : Input) (result : Output) : Decidable (∃ S : Finset Int, (S.card = input.2 ∧ List.Nodup result ∧ List.toFinset result = S) ∧ (∀ x ∈ S, x ∈ input.1) ∧ ∀ x ∈ S, ∀ y ∈ input.1, y ∉ S → Freq input.1 x > Freq input.1 y) := decidable_of_iff (List.Nodup result ∧ (List.toFinset result).card = input.2 ∧ (∀ x ∈ result, x ∈ input.1) ∧ ∀ x ∈ result, ∀ y ∈ input.1, y ∉ result → Freq input.1 x > Freq input.1 y) (by constructor · rintro ⟨hnd, hcard, hmem, hsep⟩ refine ⟨List.toFinset result, ⟨hcard, hnd, rfl⟩, ?_, ?_⟩ · intro x hx exact hmem x (by simpa using hx) · intro x hx y hy hys exact hsep x (by simpa using hx) y hy (by simpa using hys) · rintro ⟨S, ⟨hcard, hnd, hset⟩, hmem, hsep⟩ refine ⟨hnd, ?_, ?_, ?_⟩ · simpa [hset] using hcard · intro x hx exact hmem x (by simpa [← hset] using hx) · intro x hx y hy hys exact hsep x (by simpa [← hset] using hx) y hy (by simpa [← hset] using hys)) /-- Executable checker obtained mechanically from the specification. -/ def topKFrequent_check (input : Input) (result : Output) : Bool := @decide (topKFrequent_spec input result) (by unfold topKFrequent_spec; infer_instance) /-- On valid input the checker accepts exactly the specified outputs. -/ theorem topKFrequent_check_iff_spec (input : Input) (result : Output) (h : isValidInput input) : topKFrequent_check input result ↔ topKFrequent_spec input result := by simp [topKFrequent_check] /-! ### Implementation helpers -/ /-- Frequency table over the fixed range [-10000, 10000], indexed by value offset, built in one pass. -/ def freqTable (nums : List Int) : Array Nat := nums.foldl (fun t x => let i := (x + 10000).toNat t.set! i (t.getD i 0 + 1)) (Array.replicate 20001 0) /-- Values with positive counts, sorted by count descending with ties broken by ascending value. -/ def valuesSortedByFreq (t : Array Nat) : List Int := let pairs := (List.range 20001).filterMap (fun i => if t.getD i 0 > 0 then some (i, t.getD i 0) else none) let sorted := pairs.toArray.qsort (fun a b => decide (b.2 < a.2) || (a.2 == b.2 && decide (a.1 < b.1))) sorted.toList.map (fun p => (p.1 : Int) - 10000) /-! ### Main algorithm (impl) -/ /-- The k most frequent elements by a one-pass fixed-range count, a descending frequency sort, and a take. -/ def topKFrequentElements (input : Input) : Output := (valuesSortedByFreq (freqTable input.1)).take input.2 /-! ### Correctness -/ /-- On valid input the algorithm meets the specification. -/ theorem topKFrequentElements_correct (input : Input) (h : isValidInput input) : topKFrequent_spec input (topKFrequentElements input) := by sorry /-! ## Unit tests -/ /-! ### L1 — Validity guard (V accepts the provided examples) -/ #guard isValidInput ([1, 1, 1, 2, 2, 3], 2) #guard isValidInput ([1], 1) #guard isValidInput ([1, 2], 2) /-! ### L1b — Negative validity (V rejects invalid input) -/ #guard !(isValidInput ([10001], 1)) #guard !(isValidInput ([1, 1, 2, 2], 1)) #guard !(isValidInput ([1, 2], 0)) /-! ### L2 — Specification guard (P_check accepts the correct output) -/ #guard topKFrequent_check ([1, 1, 1, 2, 2, 3], 2) [1, 2] #guard topKFrequent_check ([1], 1) [1] #guard topKFrequent_check ([1, 2], 2) [1, 2] /-! ### L2b — Negative specification (P_check rejects a wrong output) -/ #guard !(topKFrequent_check ([1, 1, 1, 2, 2, 3], 2) [1, 3]) #guard !(topKFrequent_check ([1], 1) [1, 1]) #guard !(topKFrequent_check ([1, 2], 2) [1]) /-! ### L3 — Algorithm output (impl matches the expected output) -/ #guard topKFrequentElements ([1, 1, 1, 2, 2, 3], 2) == [1, 2] #guard topKFrequentElements ([1], 1) == [1] #guard topKFrequentElements ([1, 2], 2) == [1, 2] /-! ### L4 — Integration (P_check certifies the output of impl) -/ #guard topKFrequent_check ([1, 1, 1, 2, 2, 3], 2) (topKFrequentElements ([1, 1, 1, 2, 2, 3], 2)) #guard topKFrequent_check ([1], 1) (topKFrequentElements ([1], 1)) #guard topKFrequent_check ([1, 2], 2) (topKFrequentElements ([1, 2], 2)) end PTopKFrequentElements