Lexicographically smallest negated permutation that sums to target

Array Math Two Pointers Greedy Sorting

30.8% acceptance

Feb 25, 2026

You are given a positive integer n and an integer target. Return the lexicographically smallest array of integers of size n such that: The sum of its elements equals target. The absolute values of its elements form a permutation of size n. If no such array exists, return an empty array. A permutation of size n is a rearrangement of integers 1, 2, ..., n.

Solution

Rust

Time O(n log n)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn lex_smallest_negated_perm(n: i32, target: i64) -> Vec<i32> {
    let total = n as i64 * (n as i64 + 1) / 2;
    let diff = total - target;
    if diff < 0 || diff % 2 != 0 || diff > 2 * total { return vec![]; }
    let mut d = diff / 2;
    let mut negated = std::collections::HashSet::new();
    let mut i = n;
    while d > 0 && i >= 1 {
      if d >= i as i64 {
        negated.insert(i);
        d -= i as i64;
      } else {
        negated.insert(d as i32);
        d = 0;
      }
      i -= 1;
    }
    if d > 0 { return vec![]; }
    let mut neg_vals: Vec<i32> = negated.iter().map(|&v| -v).collect();
    let pos_vals: Vec<i32> = (1..=n).filter(|v| !negated.contains(v)).collect();
    neg_vals.sort();
    let mut result = neg_vals;
    result.extend(pos_vals);
    result
  }
}