1649

1649. Create Sorted Array through Instructions (Hard)

Given an integer array instructions, you are asked to create a sorted array from the elements in instructions. You start with an empty container nums. For each element from left to right in instructions, insert it into nums. The cost of each insertion is the minimum of the following:

• The number of elements currently in nums that are strictly less than instructions[i].
• The number of elements currently in nums that are strictly greater than instructions[i].

For example, if inserting element 3 into nums = [1,2,3,5], the cost of insertion is min(2, 1) (elements 1 and 2 are less than 3, element 5 is greater than 3) and nums will become [1,2,3,3,5].

Return the total cost to insert all elements from instructions into nums. Since the answer may be large, return it modulo 109 + 7

 

Example 1:

Input: instructions = [1,5,6,2]
Output: 1
Explanation: Begin with nums = [].
Insert 1 with cost min(0, 0) = 0, now nums = [1].
Insert 5 with cost min(1, 0) = 0, now nums = [1,5].
Insert 6 with cost min(2, 0) = 0, now nums = [1,5,6].
Insert 2 with cost min(1, 2) = 1, now nums = [1,2,5,6].
The total cost is 0 + 0 + 0 + 1 = 1.

Example 2:

Input: instructions = [1,2,3,6,5,4]
Output: 3
Explanation: Begin with nums = [].
Insert 1 with cost min(0, 0) = 0, now nums = [1].
Insert 2 with cost min(1, 0) = 0, now nums = [1,2].
Insert 3 with cost min(2, 0) = 0, now nums = [1,2,3].
Insert 6 with cost min(3, 0) = 0, now nums = [1,2,3,6].
Insert 5 with cost min(3, 1) = 1, now nums = [1,2,3,5,6].
Insert 4 with cost min(3, 2) = 2, now nums = [1,2,3,4,5,6].
The total cost is 0 + 0 + 0 + 0 + 1 + 2 = 3.

Example 3:

Input: instructions = [1,3,3,3,2,4,2,1,2]
Output: 4
Explanation: Begin with nums = [].
Insert 1 with cost min(0, 0) = 0, now nums = [1].
Insert 3 with cost min(1, 0) = 0, now nums = [1,3].
Insert 3 with cost min(1, 0) = 0, now nums = [1,3,3].
Insert 3 with cost min(1, 0) = 0, now nums = [1,3,3,3].
Insert 2 with cost min(1, 3) = 1, now nums = [1,2,3,3,3].
Insert 4 with cost min(5, 0) = 0, now nums = [1,2,3,3,3,4].
​​​​​​​Insert 2 with cost min(1, 4) = 1, now nums = [1,2,2,3,3,3,4].
​​​​​​​Insert 1 with cost min(0, 6) = 0, now nums = [1,1,2,2,3,3,3,4].
​​​​​​​Insert 2 with cost min(2, 4) = 2, now nums = [1,1,2,2,2,3,3,3,4].
The total cost is 0 + 0 + 0 + 0 + 1 + 0 + 1 + 0 + 2 = 4.

 

Constraints:

• 1 <= instructions.length <= 105
• 1 <= instructions[i] <= 105

Companies: Amazon, Akuna Capital

Related Topics:
Array, Binary Search, Divide and Conquer, Binary Indexed Tree, Segment Tree, Merge Sort, Ordered Set

Similar Questions:

• Count Good Triplets in an Array (Hard)
• Longest Substring of One Repeating Character (Hard)
• Sort Array by Moving Items to Empty Space (Hard)

Solution 1. BIT

// OJ: https://leetcode.com/problems/create-sorted-array-through-instructions/
// Author: github.com/lzl124631x
// Time: O(NlogM) where M is the range of A[i]
// Space: O(M)
// Ref: https://leetcode.com/problems/create-sorted-array-through-instructions/discuss/927531/JavaC%2B%2BPython-Binary-Indexed-Tree
int c[100001] = {};
class Solution {
public:
    static inline int lowbit(int x) { return x & -x; }
    int createSortedArray(vector<int>& A) {
        memset(c, 0, sizeof(c));
        int ans = 0, N = A.size(), mod = 1e9 + 7;
        for (int i = 0; i < N; ++i) {
            ans = (ans + min(get(A[i] - 1), i - get(A[i]))) % mod;
            update(A[i]);
        }
        return ans;
    }
    void update(int x) {
        for (; x < 100001; x += lowbit(x)) c[x]++;
    }
    int get(int x) { // returns the sum of numbers <= x
        int ans = 0;
        for (; x > 0; x -= lowbit(x)) ans += c[x];
        return ans;
    }
};

In OOD fashion:

// OJ: https://leetcode.com/problems/create-sorted-array-through-instructions
// Author: github.com/lzl124631x
// Time: O(NlogM) where M is the range of A[i]
// Space: O(M)
class BIT {
    vector<int> node;
    static inline int lb(int x) { return x & -x; }
public:
    BIT(int N) : node(N + 1) {}
    int query(int i) { // query(i) is the count of numbers <= i. 0 <= i <= 1e5`
        int ans = 0;
        for (++i; i; i -= lb(i)) ans += node[i];
        return ans;
    }
    void update(int i, int delta) {
        for (++i; i < node.size(); i += lb(i)) node[i] += delta;
    }
};
class Solution {
public:
    int createSortedArray(vector<int>& A) {
        long N = A.size(), mod = 1e9 + 7, ans = 0;
        BIT tree(100001); 
        for (int i = 0; i < N; ++i) {
            long lt = tree.query(A[i] - 1), gt = i - tree.query(A[i]);
            ans = (ans + min(lt, gt)) % mod;
            tree.update(A[i], 1);
        }
        return ans;
    }
};

Solution 2. Divide and Conquer

// OJ: https://leetcode.com/problems/create-sorted-array-through-instructions/
// Author: github.com/lzl124631x
// Time: O(NlogN)
// Space: O(N)
const int maxN = 100001;
int id[maxN], lt[maxN], gt[maxN], tmp[maxN];
class Solution {
    void solve(vector<int> &A, int begin, int end) {
        if (begin + 1 >= end) return;
        int mid = (begin + end) / 2, i = begin, j = mid, k = begin;
        solve(A, begin, mid);
        solve(A, mid, end);
        for (; j < end; ++j) {
            while (i < mid && A[id[i]] < A[id[j]]) ++i;
            lt[id[j]] += i - begin;
        }
        for (i = mid - 1, j = end - 1; j >= mid; --j) {
            while (i >= begin && A[id[i]] > A[id[j]]) --i;
            gt[id[j]] += mid - i - 1;
        }
        for (i = begin, j = mid; i < mid || j < end;) {
            if (j >= end || (i < mid && A[id[i]] < A[id[j]])) tmp[k++] = id[i++];
            else tmp[k++] = id[j++];
        }
        for (i = begin; i < end; ++i) id[i] = tmp[i];
    }
public:
    int createSortedArray(vector<int>& A) {
        long N = A.size(), ans = 0, mod = 1e9 + 7;
        iota(begin(id), begin(id) + N, 0);
        memset(lt, 0, sizeof(lt));
        memset(gt, 0, sizeof(lt));
        solve(A, 0, N);
        for (int i = 0; i < N; ++i) ans = (ans + min(lt[i], gt[i])) % mod;
        return ans;
    }
};