import Mathlib /-! # Squares Of A Sorted Array Given an integer array nums sorted in non-decreasing order, return an array of the squares of each number sorted in non-decreasing order. ## Constraints - 1 <= nums.length <= 10^4 - -10^4 <= nums[i] <= 10^4 - nums is sorted in non-decreasing order. ## Provided examples - `nums = [-4, -1, 0, 3, 10]` → `[0, 1, 9, 16, 100]` - `nums = [-7, -3, 2, 3, 11]` → `[4, 9, 9, 49, 121]` - `nums = [0]` → `[0]` ## Synthesized negative examples - invalid input: `nums = []` ([structural] a predicate that admits 1 <= nums.length <= 10^4. empty array is below the length floor) - invalid input: `nums = [10001]` ([structural] a predicate that admits -10^4 <= nums[i] <= 10^4. one above the upper value bound) - invalid input: `nums = [1, 0]` ([structural] a predicate that admits nums is sorted in non-decreasing order.. first pair decreases, breaking sorted order) - `nums = [-4, -1, 0, 3, 10]` → `[16, 1, 0, 9, 100]` is wrong ([structural] the output is not required to be sorted; any order of the squares is accepted. all entries are the correct squares, only sortedness is dropped) - `nums = [-7, -3, 2, 3, 11]` → `[49, 9, 4, 9, 121]` is wrong ([structural] non-decreasing order is not required. squares in input order; only sortedness fails) - `nums = [0]` → `[1]` is wrong ([structural] squares n+1 rather than n. 1 is the square of 1, not of 0; value off by one.) -/ namespace PSquaresOfASortedArray abbrev Input := List Int abbrev Output := List Int /-! ### Validity predicate (V) -/ /-- Valid input: a nonempty integer list of length at most 10^4, sorted in non-decreasing order, with every entry between -10^4 and 10^4. -/ def isValidInput (input : Input) : Bool := 1 ≤ input.length && input.length ≤ 10 ^ 4 && input.all (fun x => -10 ^ 4 ≤ x && x ≤ 10 ^ 4) && (input.zip input.tail).all (fun p => p.1 ≤ p.2) /-! ### Ideal specification (P_spec) -/ /-- `result` is the sorted list of squares: a permutation of the entrywise squares of `input` that is itself sorted in non-decreasing order. -/ def sortedSquares_spec (input : Input) (result : Output) : Prop := result.Perm (input.map (fun x => x * x)) ∧ result.SortedLE /-! ### Decidable specification (P_check) -/ /-- Executable checker for `sortedSquares_spec`: the unique sorted permutation of the entrywise squares is the insertion sort of those squares. -/ def sortedSquares_check (input : Input) (result : Output) : Bool := decide (result = List.insertionSort (· ≤ ·) (input.map (fun x => x * x))) /-- On valid input the checker accepts exactly the specified outputs. -/ theorem sortedSquares_check_iff_spec (input : Input) (result : Output) (h : isValidInput input) : sortedSquares_check input result ↔ sortedSquares_spec input result := by unfold sortedSquares_check sortedSquares_spec simp only [decide_eq_true_eq] constructor · rintro rfl exact ⟨List.perm_insertionSort _ _, List.sortedLE_insertionSort⟩ · rintro ⟨hp, hs⟩ exact (hp.trans (List.perm_insertionSort _ _).symm).eq_of_sortedLE hs List.sortedLE_insertionSort /-! ### Implementation helpers -/ /-- Splits a sorted integer list into its negative prefix and nonnegative suffix. -/ def splitSign : List Int → List Int × List Int | [] => ([], []) | x :: xs => if x < 0 then let p := splitSign xs (x :: p.1, p.2) else ([], x :: xs) /-- Merges two nondecreasing integer lists into one nondecreasing list. -/ def mergeSorted (xs ys : List Int) : List Int := match xs, ys with | [], ys => ys | xs, [] => xs | x :: xs', y :: ys' => if x ≤ y then x :: mergeSorted xs' (y :: ys') else y :: mergeSorted (x :: xs') ys' termination_by xs.length + ys.length /-! ### Main algorithm (impl) -/ /-- Squares the negative and nonnegative halves separately, then merges the two sorted square lists. -/ def sortedSquaresImpl (input : Input) : Output := let p := splitSign input let negSquares := (p.1.map (fun x => x * x)).reverse let nonnegSquares := p.2.map (fun x => x * x) mergeSorted negSquares nonnegSquares /-! ### Correctness -/ /-- On valid input the algorithm meets the specification. -/ theorem sortedSquaresImpl_correct (input : Input) (h : isValidInput input) : sortedSquares_spec input (sortedSquaresImpl input) := by sorry /-! ## Unit tests -/ /-! ### L1 — Validity guard (V accepts the provided examples) -/ #guard isValidInput [(-4), (-1), 0, 3, 10] #guard isValidInput [(-7), (-3), 2, 3, 11] #guard isValidInput [0] /-! ### 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 sortedSquares_check [(-4), (-1), 0, 3, 10] [0, 1, 9, 16, 100] #guard sortedSquares_check [(-7), (-3), 2, 3, 11] [4, 9, 9, 49, 121] #guard sortedSquares_check [0] [0] /-! ### L2b — Negative specification (P_check rejects a wrong output) -/ #guard !(sortedSquares_check [(-4), (-1), 0, 3, 10] [16, 1, 0, 9, 100]) #guard !(sortedSquares_check [(-7), (-3), 2, 3, 11] [49, 9, 4, 9, 121]) #guard !(sortedSquares_check [0] [1]) /-! ### L3 — Algorithm output (impl matches the expected output) -/ #guard sortedSquaresImpl [-4, -1, 0, 3, 10] == [0, 1, 9, 16, 100] #guard sortedSquaresImpl [-7, -3, 2, 3, 11] == [4, 9, 9, 49, 121] #guard sortedSquaresImpl [0] == [0] /-! ### L4 — Integration (P_check certifies the output of impl) -/ #guard sortedSquares_check [-4, -1, 0, 3, 10] (sortedSquaresImpl [-4, -1, 0, 3, 10]) #guard sortedSquares_check [-7, -3, 2, 3, 11] (sortedSquaresImpl [-7, -3, 2, 3, 11]) #guard sortedSquares_check [0] (sortedSquaresImpl [0]) end PSquaresOfASortedArray