Question

Formatted question description: https://leetcode.ca/all/1649.html

 1649. Create Sorted Array through Instructions

 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

Algorithm

Using a tree array, single-point modification + interval query, tree[i] represents the number of occurrences of the number i in the inserted element, and the complexity of querying the number of less than/greater than x and inserting new elements during each traversal is 𝑂(𝑙𝑜𝑔𝑁), the total complexity is 𝑂(𝑁𝑙𝑜𝑔𝑁).

Code

class Solution {
    final static int MODULO = 1000000007;
    final static int MAX = 100000;
    int[] segmentTree = new int[MAX * 2 + 1];

    public int createSortedArray(int[] instructions) {
        int cost = 0;
        int length = instructions.length;
        for (int i = 0; i < length; i++) {
            int num = instructions[i];
            int count = segmentTree[num + MAX] + 1;
            update(num, count);
            int sumRange1 = sumRange(1, num - 1), sumRange2 = sumRange(num + 1, MAX);
            cost = (cost + Math.min(sumRange1, sumRange2)) % MODULO;
        }
        return cost;
    }
    
    public void update(int i, int val) {
        int index = i + MAX;
        int prevVal = segmentTree[index];
        int difference = val - prevVal;
        while (index > 0) {
            segmentTree[index] = (segmentTree[index] + difference) % MODULO;
            index >>= 1;
        }
    }
    
    public int sumRange(int i, int j) {
        int sum = 0;
        int index1 = i + MAX, index2 = j + MAX;
        while (index1 <= index2) {
            if (index1 % 2 == 1) {
                sum = (sum + segmentTree[index1]) % MODULO;
                index1++;
            }
            if (index2 % 2 == 0) {
                sum = (sum + segmentTree[index2]) % MODULO;
                index2--;
            }
            index1 >>= 1;
            index2 >>= 1;
        }
        return sum;
    }
}

############

class Solution {
    public int createSortedArray(int[] instructions) {
        int n = 100010;
        int mod = (int) 1e9 + 7;
        BinaryIndexedTree tree = new BinaryIndexedTree(n);
        int ans = 0;
        for (int num : instructions) {
            int a = tree.query(num - 1);
            int b = tree.query(n) - tree.query(num);
            ans += Math.min(a, b);
            ans %= mod;
            tree.update(num, 1);
        }
        return ans;
    }
}

class BinaryIndexedTree {
    private int n;
    private int[] c;

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

    public void update(int x, int delta) {
        while (x <= n) {
            c[x] += delta;
            x += lowbit(x);
        }
    }

    public int query(int x) {
        int s = 0;
        while (x > 0) {
            s += c[x];
            x -= lowbit(x);
        }
        return s;
    }

    public static int lowbit(int x) {
        return x & -x;
    }
}

// OJ: https://leetcode.com/problems/create-sorted-array-through-instructions/
// 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 smaller than x
        int ans = 0;
        for (; x > 0; x -= lowbit(x)) ans += c[x];
        return ans;
    }
};

class BinaryIndexedTree:
    def __init__(self, n):
        self.n = n
        self.c = [0] * (n + 1)

    @staticmethod
    def lowbit(x):
        return x & -x

    def update(self, x, delta):
        while x <= self.n:
            self.c[x] += delta
            x += BinaryIndexedTree.lowbit(x)

    def query(self, x):
        s = 0
        while x > 0:
            s += self.c[x]
            x -= BinaryIndexedTree.lowbit(x)
        return s


class Solution:
    def createSortedArray(self, instructions: List[int]) -> int:
        n = max(instructions)
        tree = BinaryIndexedTree(n)
        ans = 0
        for num in instructions:
            a = tree.query(num - 1)
            b = tree.query(n) - tree.query(num)
            ans += min(a, b)
            tree.update(num, 1)
        return ans % int((1e9 + 7))

type BinaryIndexedTree struct {
	n int
	c []int
}

func newBinaryIndexedTree(n int) *BinaryIndexedTree {
	c := make([]int, n+1)
	return &BinaryIndexedTree{n, c}
}

func (this *BinaryIndexedTree) lowbit(x int) int {
	return x & -x
}

func (this *BinaryIndexedTree) update(x, delta int) {
	for x <= this.n {
		this.c[x] += delta
		x += this.lowbit(x)
	}
}

func (this *BinaryIndexedTree) query(x int) int {
	s := 0
	for x > 0 {
		s += this.c[x]
		x -= this.lowbit(x)
	}
	return s
}

func createSortedArray(instructions []int) int {
	n := 100010
	mod := int(1e9 + 7)
	tree := newBinaryIndexedTree(n)
	ans := 0
	for _, num := range instructions {
		a, b := tree.query(num-1), tree.query(n)-tree.query(num)
		ans += min(a, b)
		ans %= mod
		tree.update(num, 1)
	}
	return ans
}

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

1649 - Create Sorted Array through Instructions

Question

Algorithm

Code

All Problems

All Solutions

Welcome to Subscribe On Youtube

Question

Algorithm

Code

All Problems

All Solutions