Salesforce·Software Engineer·Technical Phone Screen·Intermediate

Intermediate

Jun 2026

Summary

Salesforce SWE interview with a tricky array permutation problem that looks straightforward until you actually try to get the edge cases right under pressure.

Questions Asked (1)

Given an array of positive integers, return the lexicographically largest permutation that is strictly smaller than the input and can be produced by swapping exactly two elements. If no such permutation exists, return the original array.

Algorithms & Data Structures

Author's notes

The core scan isn't hard once you know to go right to left looking for a drop.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

To find the lexicographically largest permutation strictly smaller than the input using exactly one swap, scan from right to left to find the first position where a smaller element exists to its right. Then, swap it with the largest element to its right that is still smaller than it, ensuring the result is as large as possible while remaining smaller. If no such position exists, return the original array.

Pro tip: Clarify that the swap must be exactly one swap and the result must be strictly smaller; this avoids off-by-one errors and ensures you handle edge cases like already minimal permutations. Also, mention that the algorithm runs in O(n) time, which is optimal.

1. Understand the problem and constraints

Restate the problem: find the lexicographically largest permutation strictly smaller than the input using exactly one swap. Confirm that if no such permutation exists, return the original array.

2. Identify the rightmost swappable position

Scan the array from right to left to find the first index i where there exists an element to its right that is smaller than arr[i]. This is the position where a swap can produce a smaller permutation.

3. Find the best swap candidate

Among elements to the right of i, find the largest element that is still smaller than arr[i]. If there are duplicates, choose the rightmost occurrence to maximize the resulting permutation.

4. Perform the swap and return

Swap arr[i] with the chosen element. The resulting array is the lexicographically largest permutation strictly smaller than the input. If no such i exists, return the original array.

5. Analyze complexity and edge cases

Discuss time complexity O(n) and space O(1). Mention edge cases: array of size 1, strictly increasing array (no swap possible), and arrays with duplicates.

Key Points to Mention

Lexicographical order comparison and how it relates to array permutations.
The importance of scanning from right to left to find the first swappable position.
Selecting the largest possible smaller element to maximize the permutation.
Handling duplicates by choosing the rightmost occurrence of the candidate.
Time and space complexity analysis: O(n) time, O(1) space.
Edge cases: no valid swap, single-element array, and arrays with repeated elements.

AI-generated suggestions, not part of the candidate's original notes. May be inaccurate — verify before relying on them.