1649. Create Sorted Array through Instructions LeetCode Solution
In this guide, you will get 1649. Create Sorted Array through Instructions LeetCode Solution with the best time and space complexity. The solution to Create Sorted Array through Instructions problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Table of Contents
- Problem Statement
- Complexity Analysis
- Create Sorted Array through Instructions solution in C++
- Create Sorted Array through Instructions solution in Java
- Create Sorted Array through Instructions solution in Python
- Additional Resources
Problem Statement of 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
Complexity Analysis
- Time Complexity: O(n\log\max(\texttt{instructions}))
- Space Complexity: O(\max(\texttt{instructions}))
1649. Create Sorted Array through Instructions LeetCode Solution in C++
class FenwickTree {
public:
FenwickTree(int n) : sums(n + 1) {}
void add(int i, int delta) {
while (i < sums.size()) {
sums[i] += delta;
i += lowbit(i);
}
}
int get(int i) const {
int sum = 0;
while (i > 0) {
sum += sums[i];
i -= lowbit(i);
}
return sum;
}
private:
vector<int> sums;
static inline int lowbit(int i) {
return i & -i;
}
};
class Solution {
public:
int createSortedArray(vector<int>& instructions) {
constexpr int kMod = 1'000'000'007;
const int mx = ranges::max(instructions);
int ans = 0;
FenwickTree tree(mx);
for (int i = 0; i < instructions.size(); ++i) {
ans += min(tree.get(instructions[i] - 1), i - tree.get(instructions[i]));
ans %= kMod;
tree.add(instructions[i], 1);
}
return ans;
}
};
/* code provided by PROGIEZ */1649. Create Sorted Array through Instructions LeetCode Solution in Java
template <typename NodeType, typename ValueType>
class SegmentTree {
public:
explicit SegmentTree(const int n, const NodeType& defaultNode)
: n(n), defaultNode(defaultNode), tree(4 * n) {}
// Adds nums[i] to val equivalently.
void add(int i, ValueType val) {
add(0, 0, n - 1, i, val);
}
// Returns the result of the range query from nums[i..j].
NodeType query(int i, int j) const {
return query(0, 0, n - 1, i, j);
}
protected:
// Merges the result of the left node and the right node.
virtual NodeType merge(const NodeType& a, const NodeType& b) const = 0;
virtual NodeType makeLeafNode(ValueType val) const = 0;
private:
const int n; // the size of the input array
const NodeType defaultNode; // default node value for non-overlapping queries
vector<NodeType> tree; // the segment tree
void add(int treeIndex, int lo, int hi, int i, ValueType val) {
if (lo == hi) {
tree[treeIndex] += makeLeafNode(val);
return;
}
const int mid = (lo + hi) / 2;
if (i <= mid)
add(2 * treeIndex + 1, lo, mid, i, val);
else
add(2 * treeIndex + 2, mid + 1, hi, i, val);
tree[treeIndex] = merge(tree[2 * treeIndex + 1], tree[2 * treeIndex + 2]);
}
NodeType query(int treeIndex, int lo, int hi, int i, int j) const {
if (i <= lo && hi <= j) // [lo, hi] lies completely inside [i, j].
return tree[treeIndex];
if (j < lo || hi < i) // [lo, hi] lies completely outside [i, j].
return defaultNode;
const int mid = (lo + hi) / 2;
return merge(query(2 * treeIndex + 1, lo, mid, i, j),
query(2 * treeIndex + 2, mid + 1, hi, i, j));
}
};
class SumSegmentTree : public SegmentTree<int, int> {
public:
explicit SumSegmentTree(int n) : SegmentTree(n, 0) {}
protected:
int merge(const int& a, const int& b) const override {
return a + b;
}
int makeLeafNode(int val) const override {
return val;
}
};
class Solution {
public:
int createSortedArray(vector<int>& instructions) {
constexpr int kMod = 1'000'000'007;
const int mx = ranges::max(instructions);
int ans = 0;
SumSegmentTree tree(mx + 1);
for (const int i : instructions) {
ans += min(tree.query(0, i - 1), tree.query(i + 1, mx));
ans %= kMod;
tree.add(i, 1);
}
return ans;
}
};
// code provided by PROGIEZ1649. Create Sorted Array through Instructions LeetCode Solution in Python
struct Item {
int num;
int index;
};
class Solution {
public:
int createSortedArray(vector<int>& instructions) {
constexpr int kMod = 1'000'000'007;
const int n = instructions.size();
int ans = 0;
vector<Item> items;
// lesser[i] := the number of numbers < instructions[i]
vector<int> lesser(n);
// greater[i] := the number of numbers > instructions[i]
vector<int> greater(n);
for (int i = 0; i < n; ++i)
items.push_back({instructions[i], i});
mergeSort(items, 0, n - 1, lesser, greater);
for (int i = 0; i < n; ++i) {
ans += min(lesser[i], greater[i]);
ans %= kMod;
}
return ans;
}
private:
void mergeSort(vector<Item>& items, int l, int r, vector<int>& lesser,
vector<int>& greater) {
if (l >= r)
return;
const int m = (l + r) / 2;
mergeSort(items, l, m, lesser, greater);
mergeSort(items, m + 1, r, lesser, greater);
merge(items, l, m, r, lesser, greater);
}
void merge(vector<Item>& items, int l, int m, int r, vector<int>& lesser,
vector<int>& greater) {
int lo = l; // the first index s.t. items[lo].num >= items[i].num
int hi = l; // the first index s.t. items[hi].num > items[i].num
for (int i = m + 1; i <= r; ++i) {
while (lo <= m && items[lo].num < items[i].num)
++lo;
while (hi <= m && items[hi].num <= items[i].num)
++hi;
lesser[items[i].index] += lo - l;
greater[items[i].index] += m - hi + 1;
}
vector<Item> sorted(r - l + 1);
int k = 0; // sorted's index
int i = l; // left's index
int j = m + 1; // right's index
while (i <= m && j <= r)
if (items[i].num < items[j].num)
sorted[k++] = items[i++];
else
sorted[k++] = items[j++];
// Put the possible remaining left part into the sorted array.
while (i <= m)
sorted[k++] = items[i++];
// Put the possible remaining right part into the sorted array.
while (j <= r)
sorted[k++] = items[j++];
copy(sorted.begin(), sorted.end(), items.begin() + l);
}
};
# code by PROGIEZAdditional Resources
- Explore all LeetCode problem solutions at Progiez here
- Explore all problems on LeetCode website here
Happy Coding! Keep following PROGIEZ for more updates and solutions.