LeetCode Problem 3752

Difficulty: 🟡 Medium
Topics: Array, Math, Two Pointers, Greedy, Sorting

Solution

LeetCode 3752: Lexicographically Smallest Negated Permutation that Sums to Target

Problem Understanding

We are given two values:

• n, which determines the numbers 1, 2, ..., n
• target, which is the required sum of the final array

We must construct an array of length n whose absolute values are exactly the numbers 1 through n, each used once.

This means every number from 1 to n appears exactly once, either as a positive value or as a negative value. For example, when n = 4, valid absolute values are:

{1, 2, 3, 4}

Possible arrays include:

• [1, 2, 3, 4]
• [-1, 2, -3, 4]
• [-4, -3, -2, -1]

but not:

• [1, 1, 2, 4] because absolute values are not a permutation
• [1, 2, 3] because size is wrong

Among all valid arrays whose sum equals target, we must return the lexicographically smallest one.

Recall that lexicographical comparison examines elements from left to right. The first position where two arrays differ determines which array is smaller. Therefore, making earlier elements as small as possible is always beneficial.

The constraints are important:

• n can be as large as 100000
• target can be as large as 10^10 in magnitude

Because n is large, any solution involving permutation generation or exponential search is impossible. We need an algorithm that is essentially linear or near linear.

Several edge cases immediately stand out:

• The requested target may be impossible to achieve.
• n = 1 has only two possible arrays: [1] and [-1].
• The target may equal the maximum possible sum.
• The target may equal the minimum possible sum.
• The target may have the wrong parity, making it unattainable even though it lies within the numerical range.

Understanding the structure of achievable sums is the key to solving the problem efficiently.

Approaches

Brute Force

A brute force solution would consider every possible sign assignment.

For each number i from 1 to n, we decide whether it appears as +i or -i. Since there are n independent choices, there are:

$$2^n$$

possible sign configurations.

For each configuration we could:

1. Compute its sum.
2. Keep only those whose sum equals target.
3. Generate the corresponding lexicographically smallest ordering.
4. Return the minimum among all candidates.

This approach is correct because it explicitly enumerates every valid possibility.

However, even for n = 50, the search space is astronomically large. With n = 100000, it is completely infeasible.

Key Insight

Let

$$S = 1 + 2 + \cdots + n = \frac{n(n+1)}{2}$$

Initially, if all numbers are positive, the sum is S.

Suppose we negate a subset whose values add up to X.

Each negated value changes the total sum by:

$$-i - (+i) = -2i$$

Therefore the final sum becomes:

$$S - 2X$$

To achieve target, we need:

$$S - 2X = target$$

which implies

$$X = \frac{S - target}{2}$$

Therefore:

1. A solution exists only if S - target is nonnegative and even.
2. We merely need to choose a subset of {1,...,n} whose sum equals X.

Now consider lexicographic order.

The first position of the final array corresponds to value n, then n-1, and so on.

Why?

Because if we place -n first, that is the smallest possible first element. If we can legally make it negative while still achieving the target, lexicographic optimality demands that we do so.

More generally, processing numbers from largest to smallest, we should negate a number whenever doing so still allows the remaining required subset sum to be formed using smaller numbers.

The numbers 1..k can form every sum from 0 to:

$$\frac{k(k+1)}{2}$$

This classical property lets us greedily decide whether to include each value.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(2^n)	O(n)	Enumerates all sign assignments
Optimal	O(n)	O(n)	Greedy subset construction using reachability range property

Algorithm Walkthrough

Step 1

Compute

$$S = \frac{n(n+1)}{2}$$

which is the sum when all numbers are positive.

Step 2

Check whether the target is achievable.

From

$$X=\frac{S-target}{2}$$

we require:

• S - target >= 0
• S - target is even

If either condition fails, return an empty array.

Step 3

Let

$$need = \frac{S-target}{2}$$

This is the total value that must be negated.

Step 4

Process values from n down to 1.

At value v, decide whether v belongs to the negated subset.

The remaining smaller values are:

$$1,2,\ldots,v-1$$

Their maximum achievable sum is:

$$remainMax = \frac{(v-1)v}{2}$$

If we include v, the remaining required amount becomes:

$$need-v$$

This choice is feasible exactly when:

$$need \ge v$$

and

$$need-v \le remainMax$$

If feasible, negate v.

Otherwise keep v positive.

Step 5

Store the sign decision.

If v is chosen for the subset, place -v into the answer. Otherwise place v.

Step 6

Continue until reaching 1.

The resulting array is already ordered as:

$$[n,n-1,\ldots,1]$$

with appropriate signs attached.

Step 7

Return the constructed array.

Why it works

At each step we try to make the current element as small as possible. Since a negative value is always smaller than the corresponding positive value, lexicographic optimality prefers negation whenever it remains feasible.

The feasibility test is exact because the numbers 1..k can generate every sum in the interval [0, k(k+1)/2]. Therefore if the remaining requirement fits inside that interval, a completion always exists.

Consequently, the greedy choice never destroys solvability, and whenever a negative sign is possible it is chosen. This guarantees both correctness and lexicographic minimality.

Python Solution

from typing import List

class Solution:
    def lexSmallestNegatedPerm(self, n: int, target: int) -> List[int]:
        total = n * (n + 1) // 2
        diff = total - target

        if diff < 0 or diff % 2 != 0:
            return []

        need = diff // 2
        ans = []

        for v in range(n, 0, -1):
            remain_max = (v - 1) * v // 2

            if need >= v and need - v <= remain_max:
                ans.append(-v)
                need -= v
            else:
                ans.append(v)

        return ans

The implementation begins by computing the maximum possible positive sum total.

Using the equation

$$need=(total-target)/2$$

it immediately checks whether a solution is possible. If the parity or range conditions fail, the method returns an empty array.

The variable need tracks how much value still must be assigned negative signs.

The main loop iterates from n down to 1. For each value v, the code checks whether choosing v as negative still leaves a realizable remainder. The quantity remain_max represents the largest sum obtainable using smaller numbers.

Whenever inclusion remains feasible, the algorithm chooses -v. This is the lexicographically optimal choice because it makes the current position smaller.

Otherwise v stays positive.

The resulting array is returned directly.

Go Solution

func lexSmallestNegatedPerm(n int, target int64) []int {
	total := int64(n) * int64(n+1) / 2
	diff := total - target

	if diff < 0 || diff%2 != 0 {
		return []int{}
	}

	need := diff / 2
	ans := make([]int, 0, n)

	for v := n; v >= 1; v-- {
		remainMax := int64(v-1) * int64(v) / 2

		if need >= int64(v) && need-int64(v) <= remainMax {
			ans = append(ans, -v)
			need -= int64(v)
		} else {
			ans = append(ans, v)
		}
	}

	return ans
}

The Go version follows exactly the same logic as the Python solution.

The main implementation difference is the use of int64 for arithmetic involving target, total, and need. This avoids overflow concerns and matches the function signature.

When no solution exists, the function returns an empty slice []int{}.

Worked Examples

Example 1

Input:

n = 3
target = 0

Compute:

$$S=1+2+3=6$$

$$need=(6-0)/2=3$$

v	need before	remainMax	Negate?	need after	Result
3	3	3	Yes	0	[-3]
2	0	1	No	0	[-3, 2]
1	0	0	No	0	[-3, 2, 1]

Output:

[-3, 2, 1]

Verification:

$$-3+2+1=0$$

Among all valid solutions, this is lexicographically smallest because the first element is minimized to -3.

Example 2

Input:

n = 1
target = 10000000000

Compute:

$$S=1$$

$$S-target<0$$

No solution exists.

Output:

[]

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Single pass from n down to 1
Space	O(n)	Output array contains n elements

The algorithm performs constant work for each integer from n down to 1. No sorting, recursion, or auxiliary data structures are required. Apart from the output itself, only a few variables are maintained.

Test Cases

sol = Solution()

assert sol.lexSmallestNegatedPerm(3, 0) == [-3, 2, 1]  # sample case

assert sol.lexSmallestNegatedPerm(1, 1) == [1]  # only positive value
assert sol.lexSmallestNegatedPerm(1, -1) == [-1]  # only negative value
assert sol.lexSmallestNegatedPerm(1, 0) == []  # impossible parity

assert sol.lexSmallestNegatedPerm(2, 3) == [2, 1]  # all positive
assert sol.lexSmallestNegatedPerm(2, -3) == [-2, -1]  # all negative

assert sol.lexSmallestNegatedPerm(2, 0) == []  # impossible target

assert sol.lexSmallestNegatedPerm(3, 6) == [3, 2, 1]  # maximum sum
assert sol.lexSmallestNegatedPerm(3, -6) == [-3, -2, -1]  # minimum sum

assert sol.lexSmallestNegatedPerm(4, 4) == [-4, 3, 2, 1]  # single large negation

assert sol.lexSmallestNegatedPerm(5, 1) == [-5, -4, 3, 2, 1]  # multiple negations

assert sol.lexSmallestNegatedPerm(100000, 0) != []  # large n stress test

Test Summary

Test	Why
(3, 0)	Basic example
(1, 1)	Smallest positive case
(1, -1)	Smallest negative case
(1, 0)	Impossible parity
(2, 3)	Maximum achievable sum
(2, -3)	Minimum achievable sum
(2, 0)	Unreachable target
(3, 6)	All numbers positive
(3, -6)	All numbers negative
(4, 4)	Greedy selection of largest value
(5, 1)	Multiple negated values
(100000, 0)	Performance stress test

Edge Cases

Target Larger Than the Maximum Possible Sum

The largest achievable sum occurs when every number is positive:

$$S=\frac{n(n+1)}{2}$$

If target > S, no sign assignment can reach it. The implementation detects this because diff = S - target becomes negative and immediately returns an empty array.

Incorrect Parity

Every negation changes the total sum by an even amount, namely 2i. Therefore every achievable sum has the same parity as S.

If S - target is odd, the required subset sum would not be an integer. The implementation checks diff % 2 != 0 and returns an empty array.

All Numbers Must Be Negative

When

$$target=-S$$

the required negated subset sum is exactly S.

The greedy procedure successfully chooses every value from n down to 1, producing the array:

[-n, -(n-1), ..., -1]

which is both valid and lexicographically smallest.

Very Large n

With n = 100000, any exponential or sorting-heavy approach would fail. The solution performs only one linear scan and constant-time arithmetic per element, making it easily fast enough for the maximum constraint.