minimum operations to find sort order [closed]

Question

The task description is:

I have an array of distinct numbers from 1 to n, for example arr = [5, 3, 4, 1, 2]

Initialize a variable called order to 1, now run through the arr from left to right and look for element that matches with variable order, if found increment order and move forward. In other words we can say Initialize a variable called order to 1 so first go through array from left to right and see where 1 appears in array, then increment order to 2, then move forward in array and look for 2 , if found increment order to 3. Iterating from left to right like above is called an operation

for when arr = [5,3,4,1,2], in one pass from left to right, order changes its value from 1 to 2 when arr[3] is found and then 2 to 3 when arr[4] is found

Repeat above steps until the variable order reaches value n. Number of repetitions is called operations.

So when arr [ 5,3,4,1,2], minimum number of operations required is 3

import java.util.*;

class Main {
    public static int solve(List<Integer> arr) {
        int n = arr.size();
        int order = 0; // Number of sorted items found
        int operations = 0;  // Count of full array scan
        
        while (sortedCount < n) {
            order++;
            for (int i = 0; i < n; i++) {
                if (arr.get(i) == order + 1) {
                    order++;
                }
            }
        }        
        return operations;
    }

    public static void main(String[] args) {
        System.out.println(solve(Arrays.asList(5, 3, 4, 1, 2))); // Output: 3
        System.out.println(solve(Arrays.asList(3,1,4,2,5))); // Output: 2
        System.out.println(solve(Arrays.asList(1,2,3,4))); // Output: 1
        System.out.println(solve(Arrays.asList(2,1))); // Output: 2
    }
}

My code works in time O(n^2), how can we solve this in less time complexity

Answer 1

The following algorithm solves the problem in O(n):

public static int solve(List<Integer> arr) {
    int operations = 0;
    Set<Integer> visited = new HashSet<>();
    for (int i : arr) {
        if (!visited.contains(i - 1))
           operations++;
        visited.add(i);
    }
    return operations;
}

The idea is that if you haven't seen the number - 1 before then you have to get it the next pass, so this is counting all required passes. You could use a boolean array instead of the hash set to be more performant, but it's the same complexity.

Answer 2

here is my idea

    public static int solve(List<Integer> arr) {
        int n = arr.size();
        Map<Integer, Integer> indexMap = new HashMap<>();
        
       
        for (int i = 0; i < n; i++) {
            indexMap.put(arr.get(i), i);
        }
        // we store
        //5 -> 0  
        //3 -> 1  
        //4 -> 2  
        //1 -> 3  
        //2 -> 4  
        
        int operations = 1; //we start from 1
        for (int i = 2; i <= n; i++) { // and try to find each next number (2, 3, 4, ...).
            //If index of i is bigger than index of (i - 1), we’re still good, Numbers are appearing in increasing order
            if (indexMap.get(i) < indexMap.get(i - 1)) {
                operations++; //BUT if index of i is smaller, that means we gotta restart our search (new operation needed).
            }
        }
        //One loop to build the map (O(n))
        //One loop to count operations (O(n))
        // => Total: O(n)
        return operations;
    }