New answers tagged

3

I'm assuming that you're on a RAM machine with word size $\Theta(\log N$). Keep a van Emde Boas tree $T$ storing the empty positions (integers from $1$ to $N$). Whenever you insert an element $i$, delete $i$ from $T$ (in $O(\log \log N$) time) and set NEXT to the minimum element in $T$ (in $O(1)$ time). Whenever you delete an element $i$, insert $i$ to $T$ ...


0

Label each element $m_{i,j}$ of $M$ with $(m_{i,j}, j)$ and sort all such pairs in non-decreasing order of the first element (the order on the second element can be arbitrary). We will use a data structure that maintains a dynamic collection $D$ of $n$ elements and is able to insert elements, delete elements, report the maximum element in $D$, report the ...


0

There's a linear-time algorithm to reconstruct a binary search tree given a depth-first preorder left-to-right traverse. But it seems to me that what you're looking for is an algorithm which will work with a traverse which only satisfies the property that a parent appears before its children. The algorithm you present is $O(N log N)$ on average, but worst ...


2

There is no standard term for this, as it's very language-specific whether your notion makes sense, or what it would mean exactly. For instance, Some languages have no undefined values, or no undefined values in arrays, or only undefined values for certain data types. For instance, in C, you can cast an arbitrary piece of memory to an array of integers and ...


0

there's some problem with the question.There shouldnt be n-k+1 th element rather it shiuld be (current value of n)-(current operation no.)element here's the code in c++: #include using namespace std; int main() { //perform operation n-1 times // first right rotation // then deletion of element int n; cin >> n; int arr[n]; int aux[n]; for (int i = 0; ...


Top 50 recent answers are included