3752.Lexicographically Smallest

Link: 3752. Lexicographically Smallest Negated Permutation that Sums to Target
Track: Amazon tag

Question

Restate the problem

• Given a positive int n and int target
• n is the number. n is [1, 2, ...n]

---

Method 1 - Greedy
Method 2

Method 1 - Greedy

Key Insight:

• target = total - 2*(negative number)
• Find the negate total, then loop from large to small, put large negative number at first

Approach

Complexity

• Time Complexity: O(n)
• Space Complexity: O(n)

Edge Case

Code

class Solution:
    def lexSmallestNegatedPerm(self, n: int, target: int) -> List[int]:
        
        total = n * (n + 1) // 2
        
        if target > total or target < -total:
            return []
        
        need = total - target # mistake
        if need % 2 != 0:
            return []
        
        need //= 2
 
        signal = [True] * (n + 1)
        for idx in range(n, 0, -1):
            if need >= idx:
                need -= idx
                signal[idx] = False
        
        res = []
        for idx in range(n, 0, -1):
            if not signal[idx]: # False
                res.append(-idx)
        
        for idx in range(1, n + 1):
            if signal[idx]:
                res.append(idx)
        
        return res

---

History

• Jan-07-2026 Peeked: no idea