algoadvance

Leetcode 2717. Semi

Problem Statement

You are given a 0-indexed permutation of integers nums (1-indexed) of length n. A permutation means nums contains each integer from 1 to n exactly once.

A permutation is called semi-ordered if the first number equals 1 and the last number equals n. More formally, for a permutation nums it is semi-ordered if nums[0] == 1 and nums[n - 1] == n.

You are allowed to perform any number of operations, where in each operation you can choose any two adjacent elements of nums and swap them.

Return the minimum number of operations to make nums semi-ordered.

Clarifying Questions

1. Can the input permutation ever be empty?
   • No, the length n of the permutation will be at least 1 as per the problem statement.
2. What is the range of the length n of the permutation?
   • The problem does not specify a range, but you may assume typical constraints like 1 ≤ n ≤ 10^5 for competitive programming.
3. Are duplicates allowed in the permutation?
   • No, by definition, a permutation of length n contains each integer from 1 to n exactly once.
4. Should variations of the same permutation be considered different?
   • Yes, since the problem explicitly focuses on the position of 1 and n.

Strategy

1. Find the positions of 1 and n in the array.
2. Calculate the number of adjacent swaps needed to move 1 to the start of the array (index at 0).
3. Calculate the number of adjacent swaps needed to move n to the end of the array (index at n-1).
4. Depending on whether the position of 1 is before or after n, we may need to subtract one swap because moving 1 left might free up the slot that n moves into.
5. Summing up these operations will give the minimum number of required operations.

Code

public class SemiOrderedPermutation {
    public int minOperations(int[] nums) {
        int n = nums.length;
        int index1 = -1, indexN = -1;

        // Find indices of 1 and n
        for (int i = 0; i < n; i++) {
            if (nums[i] == 1) {
                index1 = i;
            } else if (nums[i] == n) {
                indexN = i;
            }
        }

        // Calculate number of swaps needed to move 1 to the start
        int swapsFor1 = index1;

        // Calculate number of swaps needed to move n to the end
        int swapsForN = (n - 1) - indexN;

        // If 1 is before n, n moving will occupy the freed slot by moving 1
        if (index1 < indexN) {
            return swapsFor1 + swapsForN;
        } else {
            return swapsFor1 + swapsForN - 1;
        }
    }

    public static void main(String[] args) {
        SemiOrderedPermutation sol = new SemiOrderedPermutation();
        int[] nums = {2, 4, 1, 3};
        System.out.println(sol.minOperations(nums)); // Output: 3
    }
}

Time Complexity

• Finding the indices of 1 and n takes O(n).
• Calculating the number of swaps is O(1).
• Hence, the overall time complexity is O(n).

Explanation

• The algorithm efficiently finds the positions of 1 and n and computes the minimum swaps needed based on their positions.
• The edge case where 1 and n are already in proper positions is implicitly handled since the operations would result in zero swaps.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?