LeetCode 1649: Create Sorted Array through Instructions Solution

Master LeetCode problem 1649 (Create Sorted Array through Instructions), a hard 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.

1649. Create Sorted Array through Instructions

Hard

Array Binary Search Divide and Conquer Binary Indexed Tree Segment Tree Merge Sort Ordered Set

Problem Explanation

Explanation

To solve this problem, we can use a Binary Indexed Tree (BIT) also known as Fenwick Tree. We iterate over the instructions array, and for each element, we update the BIT to count how many elements are smaller than the current element and how many are larger. This information helps us calculate the cost of inserting the current element into the sorted array. We then update the BIT with the current element.

The total cost is the sum of the cost for each element. We return this sum modulo 10^9 + 7 as required.

Time Complexity:

Building the BIT: O(n log n)
Calculating the total cost: O(n log n) Overall: O(n log n)

Space Complexity: O(n) for the Binary Indexed Tree

Solution Code

class Solution {
    public int createSortedArray(int[] instructions) {
        int mod = 1000000007;
        int n = instructions.length;
        int[] count = new int[100001]; // the maximum value of an element in instructions
        FenwickTree tree = new FenwickTree(100001);
        long cost = 0;

        for (int i = 0; i < n; i++) {
            int less = tree.query(instructions[i] - 1);
            int greater = i - tree.query(instructions[i]);
            cost += Math.min(less, greater);
            cost %= mod;
            tree.update(instructions[i], 1);
        }

        return (int) cost;
    }

    class FenwickTree {
        int[] tree;
        int n;

        public FenwickTree(int n) {
            this.n = n;
            this.tree = new int[n + 1];
        }

        public void update(int i, int delta) {
            while (i <= n) {
                tree[i] += delta;
                i += i & -i;
            }
        }

        public int query(int i) {
            int sum = 0;
            while (i > 0) {
                sum += tree[i];
                i -= i & -i;
            }
            return sum;
        }
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 1649 (Create Sorted Array through Instructions)?

This page provides optimized solutions for LeetCode problem 1649 (Create Sorted Array through Instructions) 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 1649 (Create Sorted Array through Instructions)?

The time complexity for LeetCode 1649 (Create Sorted Array through Instructions) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 1649 on DevExCode?

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

Back to LeetCode Solutions