import Mathlib /-! # First Missing Positive Given an unsorted integer array nums. Return the smallest positive integer that is not present in nums. You must implement an algorithm that runs in O(n) time and uses O(1) auxiliary space. ## Constraints - 1 <= nums.length <= 10^5 - -2^31 <= nums[i] <= 2^31 - 1 ## Provided examples - `nums = [1, 2, 0]` → `3` - `nums = [3, 4, -1, 1]` → `2` - `nums = [7, 8, 9, 11, 12]` → `1` ## Synthesized negative examples - invalid input: `nums = []` ([structural] a predicate that admits 1 <= nums.length <= 10^5. empty array defeats a predicate checking only element values) - invalid input: `nums = [2147483648]` ([structural] a predicate that admits -2^31 <= nums[i] <= 2^31 - 1. one past the stated maximum) - invalid input: `nums = [-2147483649]` ([structural] a predicate that admits -2^31 <= nums[i] <= 2^31 - 1. one below the stated minimum) - `nums = [1, 2, 0]` → `1` is wrong ([structural] no requirement that the answer be absent from nums. 1 is smaller than 3 but present, so no solution reaches it) - `nums = [3, 4, -1, 1]` → `1` is wrong ([structural] the answer is not required to be absent from nums. 1 is the smallest positive integer but present) - `nums = [7, 8, 9, 11, 12]` → `2` is wrong ([structural] minimality stated as achievability alone. 2 is a missing positive but not the smallest) -/ namespace PFirstMissingPositive abbrev Input := List Int abbrev Output := Nat /-! ### Specification helpers -/ /-- `k` is a positive natural number whose cast to `Int` does not occur in `nums`. -/ def IsMissingPositive (nums : List Int) (k : Nat) : Prop := 0 < k ∧ (k : Int) ∉ nums /-! ### Validity predicate (V) -/ /-- Valid input: a nonempty list of at most 10^5 integers, each in the signed 32-bit range. -/ def isValidInput (input : Input) : Bool := 1 ≤ input.length && input.length ≤ 10 ^ 5 && input.all (fun x => -(2 ^ 31) ≤ x && x ≤ 2 ^ 31 - 1) /-! ### Ideal specification (P_spec) -/ /-- `result` is the least positive natural number whose integer counterpart does not occur in `input`: it is itself absent, and every absent positive is at least `result`. -/ def firstMissingPositive_spec (input : Input) (result : Output) : Prop := IsLeast {k | IsMissingPositive input k} result /-! ### Decidable specification (P_check) -/ /-- Decides `firstMissingPositive_spec` after unfolding: `IsLeast` expands to `result` being a missing positive together with an unbounded minimality quantifier `∀ k, IsMissingPositive input k → result ≤ k`. Since any violation of minimality occurs at some `k < result`, this is equivalent to the bounded search `∀ k < result, ¬ IsMissingPositive input k`, which `Nat.decidableBallLT` decides once the body — positivity and list membership over `Int` — is decidable. -/ instance decFirstMissingPositive (input : Input) (result : Output) : Decidable (IsLeast {k | IsMissingPositive input k} result) := decidable_of_iff ((0 < result ∧ (result : Int) ∉ input) ∧ ∀ k < result, ¬ (0 < k ∧ (k : Int) ∉ input)) (by constructor · rintro ⟨hmem, hbound⟩ refine ⟨hmem, fun b hb => ?_⟩ exact le_of_not_gt fun hlt => hbound b hlt hb · rintro ⟨hmem, hbound⟩ refine ⟨hmem, fun k hk hmiss => ?_⟩ exact absurd (hbound (show k ∈ {k | IsMissingPositive input k} from hmiss)) (not_le_of_gt hk)) /-- Executable checker obtained mechanically from the specification. -/ def firstMissingPositive_check (input : Input) (result : Output) : Bool := @decide (firstMissingPositive_spec input result) (by unfold firstMissingPositive_spec; infer_instance) /-- On valid input the checker accepts exactly the specified outputs. -/ theorem firstMissingPositive_check_iff_spec (input : Input) (result : Output) (h : isValidInput input) : firstMissingPositive_check input result ↔ firstMissingPositive_spec input result := by simp [firstMissingPositive_check] /-! ### Implementation helpers -/ /-- Places each in-range positive `x` of `nums` at index `x - 1` of a fresh array of length `n`. -/ def placeAll (nums : List Int) (n : Nat) : Array Int := nums.foldl (fun a x => if 1 ≤ x ∧ x ≤ (n : Int) then a.setIfInBounds (x.toNat - 1) x else a) (Array.replicate n 0) /-- First index of a length-`n` placed array not storing its expected value, as the answer. -/ def firstMismatch (a : Array Int) (n : Nat) : Nat := let found := (List.range n).foldl (fun acc i => if acc = 0 ∧ a.getD i 0 ≠ (i : Int) + 1 then i + 1 else acc) 0 if found = 0 then n + 1 else found /-! ### Main algorithm (impl) -/ /-- First missing positive by direct index placement of each value `x` at index `x - 1`, then a scan for the first mismatch. -/ def findFirstMissingPositive (input : Input) : Output := let n := input.length firstMismatch (placeAll input n) n /-! ### Correctness -/ /-- On valid input the algorithm meets the specification. -/ theorem findFirstMissingPositive_correct (input : Input) (h : isValidInput input) : firstMissingPositive_spec input (findFirstMissingPositive input) := by sorry /-! ## Unit tests -/ /-! ### L1 — Validity guard (V accepts the provided examples) -/ #guard isValidInput [1, 2, 0] #guard isValidInput [3, 4, (-1), 1] #guard isValidInput [7, 8, 9, 11, 12] /-! ### L1b — Negative validity (V rejects invalid input) -/ #guard !(isValidInput []) #guard !(isValidInput [2147483648]) #guard !(isValidInput [(-2147483649)]) /-! ### L2 — Specification guard (P_check accepts the correct output) -/ #guard firstMissingPositive_check [1, 2, 0] 3 #guard firstMissingPositive_check [3, 4, (-1), 1] 2 #guard firstMissingPositive_check [7, 8, 9, 11, 12] 1 /-! ### L2b — Negative specification (P_check rejects a wrong output) -/ #guard !(firstMissingPositive_check [1, 2, 0] 1) #guard !(firstMissingPositive_check [3, 4, (-1), 1] 1) #guard !(firstMissingPositive_check [7, 8, 9, 11, 12] 2) /-! ### L3 — Algorithm output (impl matches the expected output) -/ #guard findFirstMissingPositive [1, 2, 0] == 3 #guard findFirstMissingPositive [3, 4, (-1), 1] == 2 #guard findFirstMissingPositive [7, 8, 9, 11, 12] == 1 /-! ### L4 — Integration (P_check certifies the output of impl) -/ #guard firstMissingPositive_check [1, 2, 0] (findFirstMissingPositive [1, 2, 0]) #guard firstMissingPositive_check [3, 4, (-1), 1] (findFirstMissingPositive [3, 4, (-1), 1]) #guard firstMissingPositive_check [7, 8, 9, 11, 12] (findFirstMissingPositive [7, 8, 9, 11, 12]) end PFirstMissingPositive