Lexicographically Smallest Negated Permutation that Sums to Target solution and explanation
7 more videos on this problem
Lexicographically Smallest Negated Permutation Sum | LeetCode 3752 | Biweekly contest 170Sanyam IIT Guwahati · 20:59 · 1K views
Leetcode 3752 🔥 Lexicographically Smallest Negated Permutation That Sums to Target | Biweekly Contes Study Placement · 16:01 · 478 views
Leetcode 3752 | Lexicographically Smallest Negated Permutation that Sums to TargetCodeWithMeGuys · 13:36 · 253 views
Leetcode 3752. Lexicographically Smallest Negated Permutation that Sums to Target | Greedy |O(NlogN)Leet's Code · 20:31 · 162 views
3752. Lexicographically Smallest Negated Permutation that Sums to Target (Leetcode Medium)Programming Live with Larry · 20:58 · 137 views
Leetcode Biweekly Contest 170 Q3. Lexicographically Smallest Negated Permutation that Sums to TargetADevOpsEngineer · 5:25 · 126 views
LeetCode Biweekly Contest 170 | LeetCode 3750 | LeetCode 3751 | LeetCode 3752codeTips · 24:33 · 92 views
Lexicographically Smallest Negated Permutation that Sums to Target | LeetCode 3752Roy Algorithm · 20:59 · 49 views
The problem
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.
Example 1:
Input: n = 3, target = 0
Output: [-3,1,2]
Explanation:
The arrays that sum to 0 and whose absolute values form a permutation of size 3 are:
[-3, 1, 2][-3, 2, 1][-2, -1, 3][-2, 3, -1][-1, -2, 3][-1, 3, -2][1, -3, 2][1, 2, -3][2, -3, 1][2, 1, -3][3, -2, -1][3, -1, -2]
The lexicographically smallest one is [-3, 1, 2].
Example 2:
Input: n = 1, target = 10000000000
Output: []
Explanation:
There are no arrays that sum to 10000000000 and whose absolute values form a permutation of size 1. Therefore, the answer is [].
Constraints:
1 <= n <= 105-1010 <= target <= 1010
Approach overview
Problem Overview: You start with a permutation [1,2,3,...,n]. You may negate any elements (turn x into -x). The goal is to make the total sum equal to a given target while producing the lexicographically smallest resulting array.
The original sum of the permutation is S = n(n+1)/2. Negating a value x changes the total sum by -2x. If the final target is T, the total reduction needed is D = S - T. That means the values you negate must sum to D/2. The problem reduces to selecting numbers from 1..n whose sum equals D/2, while ensuring the final signed permutation is lexicographically smallest.
Approach 1: Brute Force Subset Enumeration (Exponential Time)
Enumerate every subset of numbers from 1..n and treat each subset as the elements to negate. For each subset, compute the resulting array and check whether the total equals the target. Among all valid permutations, choose the lexicographically smallest. This directly models the problem but requires checking up to 2^n subsets. Time complexity is O(2^n * n) and space complexity is O(n). Useful only for reasoning about correctness on very small inputs.
Approach 2: Dynamic Programming Subset Sum (O(n * K))
Compute K = (S - T) / 2. The task becomes a classic subset-sum problem: select numbers that sum to K. A DP table can track which sums are reachable using numbers 1..n. After computing feasible sums, reconstruct a subset that prioritizes smaller indices so the resulting signed permutation becomes lexicographically smaller. Time complexity is O(n * K) with space O(K). Works but becomes expensive when K is large.
Approach 3: Greedy Construction (Optimal, O(n))
Use a greedy strategy based on lexicographic priority. Compute K = (S - T)/2. Iterate from i = 1 to n. For each value, try negating it (which contributes i toward the subset sum). Only commit if the remaining sum K - i can still be formed using the remaining numbers. Because the remaining values form a continuous range, feasibility can be checked with simple math bounds instead of full DP. This keeps the prefix as negative as possible, making the array lexicographically smallest.
This greedy works because earlier indices dominate lexicographic order. If negating i still allows a valid completion, doing so always produces a smaller prefix. Time complexity is O(n) and space complexity is O(1).
Recommended for interviews: The greedy math approach. Interviewers expect you to recognize the transformation from sum adjustment to subset sum and then exploit the consecutive structure of 1..n. Brute force or DP shows understanding, but the greedy solution demonstrates stronger algorithmic insight using greedy, math, and array reasoning.
The written solution for this problem is still being prepared. Try it yourself in the meantime.
Try solving it yourselfComplexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Subset Enumeration | O(2^n * n) | O(n) | Conceptual baseline for very small n |
| Dynamic Programming (Subset Sum) | O(n * K) | O(K) | When you treat the task as a classic subset-sum problem |
| Greedy Math Construction | O(n) | O(1) | Optimal approach using lexicographic priority and arithmetic bounds |
Frequently asked questions
Is Lexicographically Smallest Negated Permutation that Sums to Target easy or hard?
The problem is typically rated Medium because it combines multiple ideas: permutation math, subset-sum transformation, and lexicographic ordering. Recognizing that negating x changes the sum by 2x is the key step that unlocks the greedy O(n) solution.
Lexicographically Smallest Negated Permutation that Sums to Target Python/Java solution
Most implementations follow the same greedy template: compute the required subset sum K, iterate from 1 to n, and flip the sign when feasible. This logic translates directly across Python, Java, C++, and Go with O(n) time complexity.
How to solve Lexicographically Smallest Negated Permutation that Sums to Target in O(n)?
First compute S = n(n+1)/2 and determine K = (S − target)/2. If K is negative or not an integer, no solution exists. Iterate through numbers from 1 to n and greedily negate i when K − i remains achievable using the remaining range. Update K and continue until it reaches zero.
What is the best approach for Lexicographically Smallest Negated Permutation that Sums to Target?
The optimal approach is a greedy mathematical construction. Compute the required reduction D = S − T where S = n(n+1)/2, then set K = D/2. Iterate from 1 to n and greedily negate a number if the remaining sum can still be achieved with later numbers. This produces the lexicographically smallest permutation in O(n) time and O(1) space.
Is Lexicographically Smallest Negated Permutation that Sums to Target asked at Google/Amazon/Meta?
Problems combining greedy reasoning with subset-sum style transformations frequently appear in interviews at companies like Google, Amazon, and Meta. Variants that involve lexicographic constraints and sum adjustments are common in algorithm rounds focused on arrays and greedy strategies.
What data structure is used in Lexicographically Smallest Negated Permutation that Sums to Target?
The optimal solution mainly relies on arrays and arithmetic reasoning rather than complex data structures. The permutation itself is stored in an array, while feasibility checks use simple mathematical bounds derived from the remaining numbers.
What is the time complexity of Lexicographically Smallest Negated Permutation that Sums to Target?
The optimal greedy solution runs in O(n) time because it scans the permutation once and performs constant-time feasibility checks using arithmetic bounds. Space complexity is O(1). A dynamic programming subset-sum alternative requires O(n*K) time and O(K) space.