D
DevExCode

LeetCode 3431: Minimum Unlocked Indices to Sort Nums Solution

Master LeetCode problem 3431 (Minimum Unlocked Indices to Sort Nums), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

3431. Minimum Unlocked Indices to Sort Nums

Medium
ArrayHash Table

Problem Explanation

Explanation:

To solve this problem, we need to find the minimum number of unlocked indices such that sorting the numbers at these indices will result in the given array being sorted in non-decreasing order.

We can achieve this by finding the longest increasing subsequence (LIS) from the end of the array. The length of the LIS will give us the minimum number of unlocked indices to sort the array.

Here is the step-by-step approach:

  1. Initialize an array dp of size n to store the length of the LIS ending at each index.
  2. Initialize a variable maxLength to store the maximum length of the LIS found so far.
  3. Iterate from the end of the array:
    • For each index i, iterate from i+1 to n-1:
      • If nums[j] >= nums[i], update dp[i] to max(dp[i], dp[j] + 1).
    • Update maxLength to max(maxLength, dp[i]).
  4. The minimum number of unlocked indices to sort the array will be n - maxLength.

The time complexity of this approach is O(n^2) and the space complexity is O(n).

:

Solution Code

class Solution {
    public int minUnlockedIndices(int[] nums) {
        int n = nums.length;
        int[] dp = new int[n];
        int maxLength = 0;
        
        for (int i = n - 1; i >= 0; i--) {
            dp[i] = 1;
            for (int j = i + 1; j < n; j++) {
                if (nums[j] >= nums[i]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
            maxLength = Math.max(maxLength, dp[i]);
        }
        
        return n - maxLength;
    }
}

Try It Yourself

Loading code editor...

Related LeetCode Problems

Frequently Asked Questions

How to solve LeetCode 3431 (Minimum Unlocked Indices to Sort Nums)?

This page provides optimized solutions for LeetCode problem 3431 (Minimum Unlocked Indices to Sort Nums) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 3431 (Minimum Unlocked Indices to Sort Nums)?

The time complexity for LeetCode 3431 (Minimum Unlocked Indices to Sort Nums) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 3431 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 3431 in Java, C++, or Python.

Back to LeetCode Solutions