import Mathlib /-! # Remove Duplicates From Sorted Array Given an integer array nums sorted in non-decreasing order, remove the duplicates in-place such that each unique element appears only once. The relative order of the elements should be kept the same. Then return the number of unique elements in nums. Consider the number of unique elements of nums to be k, to get accepted, you need to do the following things: Change the array nums such that the first k elements of nums contain the unique elements in the order they were present in nums initially. The remaining elements of nums are not important as well as the size of nums. Return k. 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 - -100 <= nums[i] <= 100 - nums is sorted in non-decreasing order. ## Provided examples - `nums = [1]` → `1` - `nums = [1, 1, 2]` → `2` - `nums = [-100, 100]` → `2` ## Synthesized negative examples - invalid input: `nums = []` ([structural] a predicate that admits 1 <= nums.length <= 3 * 10^4. empty where at least one element is required) - invalid input: `nums = [101]` ([structural] a predicate that admits -100 <= nums[i] <= 100. one past the stated maximum) - invalid input: `nums = [2, 1]` ([structural] a predicate that admits nums is sorted in non-decreasing order.. decreasing first pair; a predicate checking only length and values accepts it) - `nums = [1]` → `2` is wrong ([structural] specification requires all unique elements to appear in the first k but does not require only unique elements to appear. first two elements can contain 1 plus an extra) - `nums = [1, 1, 2]` → `1` is wrong ([structural] spec counts transitions between adjacent distinct values, omitting the first element. one less than the true count) - `nums = [-100, 100]` → `1` is wrong ([structural] missing soundness half: returned k need not be a realizable prefix length. below the shortest prefix that can contain both unique values) -/ namespace PRemoveDuplicatesFromSortedArray abbrev Input := List Int abbrev Output := List Int × Nat /-! ### Specification helpers -/ /-- If `x` precedes `y` in `p`, the first occurrence of `x` in `nums` precedes that of `y`. -/ def firstOccurrenceOrder (nums p : List Int) : Prop := ∀ x ∈ p, ∀ y ∈ p, p.findIdx (fun z => z == x) < p.findIdx (fun z => z == y) → nums.findIdx (fun z => z == x) < nums.findIdx (fun z => z == y) /-! ### Validity predicate (V) -/ /-- Valid input: 1 to 30000 elements, each in [-100, 100], sorted in non-decreasing order. -/ def isValidInput (input : Input) : Bool := 1 ≤ input.length && input.length ≤ 30000 && input.all (fun x => -100 ≤ x && x ≤ 100) && (input.zipWith (fun a b => decide (a ≤ b)) input.tail).all id /-! ### Ideal specification (P_spec) -/ /-- `result.1` has a prefix of length `result.2` holding exactly the values of `input`, each once, in the order of their first occurrence. -/ def removeDuplicates_spec (input : Input) (result : Output) : Prop := result.2 ≤ result.1.length ∧ ∃ p : List Int, p <+: result.1 ∧ p.length = result.2 ∧ p.Nodup ∧ (∀ x, x ∈ p ↔ x ∈ input) ∧ firstOccurrenceOrder input p /-! ### Decidable specification (P_check) -/ inductive ResultObservation where | specified (result : Output) | countOnly (count : Nat) instance coeResultObservation : Coe Output ResultObservation where coe := ResultObservation.specified instance ofNatResultObservation (count : Nat) : OfNat ResultObservation count where ofNat := ResultObservation.countOnly count /-- The array obtained by placing the unique prefix before the remaining original tail. -/ def canonicalOutput (input : Input) (count : Nat) : Output := (input.dedup ++ input.drop input.dedup.length, count) /-- Whether a specified pair has a sufficiently long array and the canonical unique prefix. -/ def acceptsSpecifiedOutput (input : Input) (result : Output) : Bool := decide (result.2 ≤ result.1.length ∧ result.2 = input.dedup.length ∧ result.1.take result.2 = input.dedup) /-- Executable checker for `removeDuplicates_spec` on a specified or count-only result. -/ def removeDuplicates_check (input : Input) (observed : ResultObservation) : Bool := match observed with | ResultObservation.specified result => acceptsSpecifiedOutput input result | ResultObservation.countOnly count => acceptsSpecifiedOutput input (canonicalOutput input count) theorem check_eq (input : Input) (result : Output) : removeDuplicates_check input result = acceptsSpecifiedOutput input result := rfl theorem idxOf_eq_findIdx (x : Int) (l : List Int) : List.idxOf x l = l.findIdx (fun z => z == x) := rfl theorem isChain_of_zipWith (l : List Int) : (l.zipWith (fun a b => decide (a ≤ b)) l.tail).all id = true → List.IsChain (· ≤ ·) l := by induction l with | nil => intro _; exact List.isChain_nil | cons x t ih => cases t with | nil => intro _; exact List.isChain_singleton x | cons y t => intro hz simp only [List.tail_cons, List.zipWith_cons_cons, List.all_cons, Bool.and_eq_true, id_eq, decide_eq_true_eq] at hz exact List.isChain_cons_cons.mpr ⟨hz.1, ih (by simpa using hz.2)⟩ theorem sorted_of_valid (input : Input) (hv : isValidInput input = true) : List.Pairwise (· ≤ ·) input := by rw [← List.isChain_iff_pairwise] refine isChain_of_zipWith input ?_ unfold isValidInput at hv simp only [Bool.and_eq_true] at hv exact hv.2 theorem rel_of_idxOf_lt {R : Int → Int → Prop} (l : List Int) (hs : List.Pairwise R l) {x y : Int} (hx : x ∈ l) (hy : y ∈ l) (hlt : List.idxOf x l < List.idxOf y l) : R x y := by have hxl : List.idxOf x l < l.length := List.idxOf_lt_length_iff.mpr hx have hyl : List.idxOf y l < l.length := List.idxOf_lt_length_iff.mpr hy have hR := List.pairwise_iff_getElem.mp hs _ _ hxl hyl hlt rwa [List.getElem_idxOf hxl, List.getElem_idxOf hyl] at hR theorem idxOf_lt_of_lt (l : List Int) (hs : List.Pairwise (· ≤ ·) l) {x y : Int} (hx : x ∈ l) (hy : y ∈ l) (hxy : x < y) : List.idxOf x l < List.idxOf y l := by rcases Nat.lt_trichotomy (List.idxOf x l) (List.idxOf y l) with hlt | heq | hgt · exact hlt · exact absurd ((List.idxOf_inj hx).mp heq) (ne_of_lt hxy) · exact absurd (rel_of_idxOf_lt l hs hy hx hgt) (by omega) theorem lt_of_idxOf_lt (l : List Int) (hs : List.Pairwise (· ≤ ·) l) {x y : Int} (hx : x ∈ l) (hy : y ∈ l) (hlt : List.idxOf x l < List.idxOf y l) : x < y := by have hle : x ≤ y := rel_of_idxOf_lt l hs hx hy hlt have hne : x ≠ y := by intro he rw [he] at hlt omega exact lt_of_le_of_ne hle hne theorem pairwise_lt_dedup (l : List Int) (hs : List.Pairwise (· ≤ ·) l) : List.Pairwise (· < ·) l.dedup := by have hle : List.Pairwise (· ≤ ·) l.dedup := List.Pairwise.sublist (List.dedup_sublist l) hs have hnd : l.dedup.Nodup := List.nodup_dedup l rw [List.pairwise_iff_getElem] at hle ⊢ intro i j hi hj hij have h1 := hle i j hi hj hij have h2 : l.dedup[i] ≠ l.dedup[j] := by intro he have := (List.Nodup.getElem_inj_iff hnd).mp he omega exact lt_of_le_of_ne h1 h2 theorem firstOccurrenceOrder_dedup (input : Input) (hs : List.Pairwise (· ≤ ·) input) : firstOccurrenceOrder input input.dedup := by intro x hx y hy hlt simp only [← idxOf_eq_findIdx] at hlt ⊢ have hxy : x < y := rel_of_idxOf_lt input.dedup (pairwise_lt_dedup input hs) hx hy hlt exact idxOf_lt_of_lt input hs (List.mem_dedup.mp hx) (List.mem_dedup.mp hy) hxy theorem pairwise_lt_of_spec (input : Input) (hs : List.Pairwise (· ≤ ·) input) (p : List Int) (hnd : p.Nodup) (hmem : ∀ x, x ∈ p ↔ x ∈ input) (hord : firstOccurrenceOrder input p) : List.Pairwise (· < ·) p := by rw [List.pairwise_iff_getElem] intro i j hi hj hij have hxi : p[i] ∈ p := List.getElem_mem hi have hxj : p[j] ∈ p := List.getElem_mem hj have h1 : List.idxOf p[i] p = i := List.Nodup.idxOf_getElem hnd i hi have h2 : List.idxOf p[j] p = j := List.Nodup.idxOf_getElem hnd j hj have hpre : List.idxOf p[i] p < List.idxOf p[j] p := by rw [h1, h2]; exact hij have hord' := hord p[i] hxi p[j] hxj (by simpa only [← idxOf_eq_findIdx] using hpre) simp only [← idxOf_eq_findIdx] at hord' exact lt_of_idxOf_lt input hs ((hmem _).mp hxi) ((hmem _).mp hxj) hord' theorem eq_dedup_of_spec (input : Input) (hs : List.Pairwise (· ≤ ·) input) (p : List Int) (hnd : p.Nodup) (hmem : ∀ x, x ∈ p ↔ x ∈ input) (hord : firstOccurrenceOrder input p) : p = input.dedup := by have h1 : List.Pairwise (· < ·) p := pairwise_lt_of_spec input hs p hnd hmem hord have h2 : List.Pairwise (· < ·) input.dedup := pairwise_lt_dedup input hs exact List.Pairwise.eq_of_mem_iff h1 h2 (fun a => by rw [hmem a, List.mem_dedup]) /-- 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 have hs := sorted_of_valid input h rw [check_eq] unfold acceptsSpecifiedOutput removeDuplicates_spec rw [decide_eq_true_eq] constructor · rintro ⟨h1, h2, h3⟩ refine ⟨h1, input.dedup, ?_, h2.symm, List.nodup_dedup input, fun x => List.mem_dedup, firstOccurrenceOrder_dedup input hs⟩ rw [← h3] exact List.take_prefix _ _ · rintro ⟨h1, p, hpre, hlen, hnd, hmem, hord⟩ have hp : p = input.dedup := eq_dedup_of_spec input hs p hnd hmem hord refine ⟨h1, ?_, ?_⟩ · rw [← hlen, hp] · rw [← hlen, ← hp] exact (List.prefix_iff_eq_take.mp hpre).symm /-! ### Implementation helpers -/ /-- First-occurrence unique elements of a sorted list, in order, by one pass that keeps only values differing from the last kept one. -/ def dedupSortedPrefix (input : List Int) : List Int := let rec go (last : Int) (acc : List Int) : List Int → List Int | [] => acc | x :: xs => if x = last then go last acc xs else go x (x :: acc) xs match input with | [] => [] | x :: xs => (go x [x] xs).reverse /-- Output equality for tests compares the unique-element counts. -/ instance beqOutput : BEq Output where beq a b := a.2 == b.2 /-- A natural number stands for the count-only output `([], count)`. -/ instance ofNatOutput (count : Nat) : OfNat Output count where ofNat := ([], count) /-! ### Main algorithm (impl) -/ /-- One left-to-right pass over the sorted input keeps the first element of each contiguous block, then pads with the original tail to restore the input's length. -/ def removeDuplicatesImpl (input : Input) : Output := let kept := dedupSortedPrefix input (kept ++ input.drop kept.length, kept.length) /-! ### Correctness -/ /-- On valid input the algorithm meets the specification. -/ theorem removeDuplicatesImpl_correct (input : Input) (h : isValidInput input) : removeDuplicates_spec input (removeDuplicatesImpl input) := by sorry /-! ## Unit tests -/ /-! ### L1 — Validity guard (V accepts the provided examples) -/ #guard isValidInput [1] #guard isValidInput [1, 1, 2] #guard isValidInput [(-100), 100] /-! ### L1b — Negative validity (V rejects invalid input) -/ #guard !(isValidInput []) #guard !(isValidInput [101]) #guard !(isValidInput [2, 1]) /-! ### L2 — Specification guard (P_check accepts the correct output) -/ #guard removeDuplicates_check [1] 1 #guard removeDuplicates_check [1, 1, 2] 2 #guard removeDuplicates_check [(-100), 100] 2 /-! ### L2b — Negative specification (P_check rejects a wrong output) -/ #guard !(removeDuplicates_check [1] 2) #guard !(removeDuplicates_check [1, 1, 2] 1) #guard !(removeDuplicates_check [(-100), 100] 1) /-! ### L3 — Algorithm output (impl matches the expected output) -/ #guard removeDuplicatesImpl [1] == 1 #guard removeDuplicatesImpl [1, 1, 2] == 2 #guard removeDuplicatesImpl [(-100), 100] == 2 /-! ### L4 — Integration (P_check certifies the output of impl) -/ #guard removeDuplicates_check [1] (removeDuplicatesImpl [1]) #guard removeDuplicates_check [1, 1, 2] (removeDuplicatesImpl [1, 1, 2]) #guard removeDuplicates_check [(-100), 100] (removeDuplicatesImpl [(-100), 100]) end PRemoveDuplicatesFromSortedArray