import Mathlib /-! # Remove Duplicates From Sorted Array Ii Given an integer array nums sorted in non-decreasing order, remove some duplicates in-place such that each unique element appears at most twice. The relative order of the elements should be kept the same. Since it is impossible to change the length of the array in some languages, you must instead have the result be placed in the first part of the array nums. More formally, if there are k elements after removing the duplicates, then the first k elements of nums should hold the final result. It does not matter what you leave beyond the first k elements. Return k after placing the final result in the first k slots of nums. Do not allocate extra space for another array. You must do this by modifying the input array in-place with O(1) extra memory. Custom Judge: The judge will test your solution with the following code: int[] nums = [...]; // Input array int[] expectedNums = [...]; // The expected answer with correct length int k = removeDuplicates(nums); // Calls your implementation assert k == expectedNums.length; for (int i = 0; i < k; i++) { assert nums[i] == expectedNums[i]; } If all assertions pass, then your solution will be accepted. ## Constraints - 1 <= nums.length <= 3 * 10^4 - -10^4 <= nums[i] <= 10^4 - nums is sorted in non-decreasing order. ## Provided examples - `nums = [1]` → `1` - `nums = [1, 1]` → `2` - `nums = [1, 1, 1]` → `2` ## Synthesized negative examples - invalid input: `nums = []` ([structural] a predicate that admits 1 <= nums.length <= 3 * 10^4. empty array below minimum length) - invalid input: `nums = [10001]` ([structural] a predicate that admits -10^4 <= nums[i] <= 10^4. one past the stated maximum value) - invalid input: `nums = [1, 0]` ([structural] a predicate that admits nums is sorted in non-decreasing order.. second element smaller than first) - `nums = [1]` → `0` is wrong ([structural] nothing requires every distinct input value to be kept. empty result satisfies at-most-twice vacuously) - `nums = [1, 1]` → `1` is wrong ([structural] maximality is not required; any k satisfying the at-most-twice condition accepted. one 1 satisfies condition but not the intended maximum) - `nums = [1, 1, 1]` → `3` is wrong ([structural] at-most-twice constraint dropped. keeping all three 1s is valid without the bound) -/ namespace PRemoveDuplicatesFromSortedArrayIi abbrev Input := List Int abbrev Output := Nat × List Int /-! ### Specification helpers -/ /-- `kept` is a subsequence of `nums` in which every integer occurs at most twice. -/ def IsAtMostTwiceSubsequence (nums kept : List Int) : Prop := List.Sublist kept nums ∧ ∀ x : Int, kept.count x ≤ 2 /-! ### Validity predicate (V) -/ /-- Valid input: 1 to 30000 elements, each in [-10^4, 10^4], sorted non-decreasingly. -/ def isValidInput (input : Input) : Bool := 1 ≤ input.length && input.length ≤ 30000 && input.all (fun x => -10000 ≤ x && x ≤ 10000) && (input.zipWith (fun a b => decide (a ≤ b)) input.tail).all id /-! ### Ideal specification (P_spec) -/ /-- `(k, arr)` is correct: `arr` is as long as the input, its first `k` slots hold an admissible kept list, and no admissible kept list is longer than `k`. -/ def removeDuplicates_spec (input : Input) (result : Output) : Prop := result.2.length = input.length ∧ (∃ kept : List Int, IsAtMostTwiceSubsequence input kept ∧ kept.length = result.1 ∧ kept <+: result.2) ∧ result.1 ∈ upperBounds {n | ∃ kept : List Int, IsAtMostTwiceSubsequence input kept ∧ kept.length = n} /-! ### Decidable specification (P_check) -/ /-- Decidable form of `IsAtMostTwiceSubsequence`: `kept` is a sublist of `nums` and every element occurs at most twice in `kept`. -/ def admissibleKept (nums kept : List Int) : Bool := decide (kept ∈ nums.sublists) && kept.all (fun x => decide (kept.count x ≤ 2)) /-- Executable checker for `removeDuplicates_spec`: the witness prefix is `result.2.take result.1`, and maximality is checked over the finitely many sublists of `input`. -/ def removeDuplicates_check (input : Input) (result : Output) : Bool := decide (result.2.length = input.length) && (admissibleKept input (result.2.take result.1) && decide ((result.2.take result.1).length = result.1)) && input.sublists.all (fun kept => !admissibleKept input kept || decide (kept.length ≤ result.1)) theorem root_of_bridges (bridge : ∀ nums kept : List Int, admissibleKept nums kept = true ↔ IsAtMostTwiceSubsequence nums kept) (input : Input) (result : Output) : removeDuplicates_check input result = true ↔ removeDuplicates_spec input result := by have prefix_bridge : (IsAtMostTwiceSubsequence input (result.2.take result.1) ∧ (result.2.take result.1).length = result.1) ↔ ∃ kept, IsAtMostTwiceSubsequence input kept ∧ kept.length = result.1 ∧ kept <+: result.2 := by constructor · rintro ⟨ha, hl⟩ exact ⟨_, ha, hl, List.take_prefix _ _⟩ · rintro ⟨kept, ha, hl, hp⟩ have he : kept = result.2.take result.1 := by simpa [hl] using (List.prefix_iff_eq_take.mp hp) simpa [← he] using And.intro ha hl simp only [removeDuplicates_check, Bool.and_eq_true, decide_eq_true_eq, List.all_eq_true, Bool.or_eq_true, Bool.not_eq_true', Bool.eq_false_iff, bridge, List.mem_sublists] rw [prefix_bridge] unfold removeDuplicates_spec simp only [upperBounds, Set.mem_setOf_eq] unfold IsAtMostTwiceSubsequence at * grind only [] theorem admissible_bridge (nums kept : List Int) : admissibleKept nums kept = true ↔ IsAtMostTwiceSubsequence nums kept := by simp only [admissibleKept, Bool.and_eq_true, decide_eq_true_eq, List.mem_sublists, List.all_eq_true, IsAtMostTwiceSubsequence] constructor · rintro ⟨hs, hc⟩ refine ⟨hs, fun x => ?_⟩ by_cases hx : x ∈ kept · exact hc x hx · simp [List.count_eq_zero_of_not_mem hx] · rintro ⟨hs, hc⟩ exact ⟨hs, fun x _ => hc x⟩ /-- On valid input the checker accepts exactly the specified outputs. -/ theorem removeDuplicates_check_iff_spec (input : Input) (result : Output) (h : isValidInput input) : removeDuplicates_check input result ↔ removeDuplicates_spec input result := by exact root_of_bridges admissible_bridge input result /-! ### Implementation helpers -/ /-- Left-to-right scan keeping only the first two occurrences of each value; `last` and `run` track the current block, `acc` the kept elements in reverse, `k` their count. -/ def scanAtMostTwice (xs : List Int) (last : Option Int) (run : Nat) (acc : List Int) (k : Nat) : List Int × Nat := match xs with | [] => (acc.reverse, k) | x :: rest => let run' := if some x = last then run + 1 else 1 if run' ≤ 2 then scanAtMostTwice rest (some x) run' (x :: acc) (k + 1) else scanAtMostTwice rest (some x) run' acc k /-- Appends the unused tail `input.drop k` to the kept prefix so the result has the input's length. -/ def padToOriginalLength (input : List Int) (kept : List Int) (k : Nat) : List Int := kept ++ input.drop k /-- A numeric literal read as an output pair, so frozen expected counts elaborate against `Output`. -/ instance outputOfNat (n : Nat) : OfNat (Nat × List Int) n := ⟨(n, [])⟩ /-- Output equality compares the kept count; the specification leaves the tail unconstrained. -/ instance outputBEq : BEq (Nat × List Int) := ⟨fun a b => a.1 == b.1⟩ /-! ### Main algorithm (impl) -/ /-- Single linear scan over the sorted list keeping at most two occurrences per value, padded back to the input length. -/ def removeDuplicatesAtMostTwice (input : Input) : Output := let (kept, k) := scanAtMostTwice input none 0 [] 0 (k, padToOriginalLength input kept k) /-! ### Correctness -/ /-- On valid input the algorithm meets the specification. -/ theorem removeDuplicatesAtMostTwice_correct (input : Input) (h : isValidInput input) : removeDuplicates_spec input (removeDuplicatesAtMostTwice input) := by sorry /-! ## Unit tests -/ /-! ### L1 — Validity guard (V accepts the provided examples) -/ #guard isValidInput [1] #guard isValidInput [1, 1] #guard isValidInput [1, 1, 1] /-! ### L1b — Negative validity (V rejects invalid input) -/ #guard !(isValidInput []) #guard !(isValidInput [10001]) #guard !(isValidInput [1, 0]) /-! ### L2 — Specification guard (P_check accepts the correct output) -/ #guard removeDuplicates_check [1] (1, [1]) #guard removeDuplicates_check [1, 1] (2, [1, 1]) #guard removeDuplicates_check [1, 1, 1] (2, [1, 1, 1]) /-! ### L2b — Negative specification (P_check rejects a wrong output) -/ #guard !(removeDuplicates_check [1] (0, [1])) #guard !(removeDuplicates_check [1, 1] (1, [1, 1])) #guard !(removeDuplicates_check [1, 1, 1] (3, [1, 1, 1])) /-! ### L3 — Algorithm output (impl matches the expected output) -/ #guard removeDuplicatesAtMostTwice [1] == 1 #guard removeDuplicatesAtMostTwice [1, 1] == 2 #guard removeDuplicatesAtMostTwice [1, 1, 1] == 2 /-! ### L4 — Integration (P_check certifies the output of impl) -/ #guard removeDuplicates_check [1] (removeDuplicatesAtMostTwice [1]) #guard removeDuplicates_check [1, 1] (removeDuplicatesAtMostTwice [1, 1]) #guard removeDuplicates_check [1, 1, 1] (removeDuplicatesAtMostTwice [1, 1, 1]) end PRemoveDuplicatesFromSortedArrayIi