New answers tagged


If you don’t know quickselect: Just implement Quicksort, but every time Quicksort would sort a sub array, you don’t do it if you don’t need it to find out which items I to j are.


I could do QuickSelect (j - i) times to get all the elements Overkill. Two calls to QuickSelect and one linear pass are sufficient.


For a normal stack, the implementation on top of a linked list is indeed questionable. Many other uses of linked lists are disappointing in practice as well. But consider a lock-free stack where push and pop are atomic. A singly-linked list can offer atomic prepend and atomic "remove head" using atomic Compare-and-Swap (some caveats apply). Implementing an ...


A priority queue does something entirely different than sorting an array. The important operations for a priority queue are: 1. Add an item to the queue. 2. Tell us the smallest item in the queue and remove it from the queue. Both these operations run in O(log n). Now use a sorted array. Operation 2 is fast if we sorted in descending order. But operation ...


Given your link, you seem to be interested in data structures supporting the following operations: Create(m): create a new instance with room for m elements. Size(): return the number of elements currently stored in the instance. Insert(k): insert an element with priority k. ExtractMax(): return the maximal priority currently stored, and remove it. Since ...


Keeping a heap is more efficient than keeping a sorted array, when you need to keep adding items to the priority queue. In case you don't need to add to it, you don't need a queue in the first place, just an array sorted by priority. Insertion to heap-based priority queue is O(logN), while insertion to sorted array is O(N) (binary search for position is O(...


Let $B[i] = A[i] + i$ and let $C[j] = A[j] - j$. You are looking for $$ \max_{i \geq j} B[i] + C[j] = \max_j (C[j] + \max_{i \geq j} B[i]). $$ This gives a linear time in-place algorithm for your problem: maxB = A[n] + n maxSum = A[n] - n + maxB for j=n-1 downto 1: maxB = max(maxB, A[j] + j) candidate = A[j] - j + maxB maxSum = max(candidate, maxSum) ...


There are two famous problems that are similar to what you're looking for. Yours comes closest to the subset sum problem Similarly we have the knapsack problem which revolves around the same idea with the general restriction that items have specific values which should also be taken into account. https://en....


Try the following algorithm: For $1 \leq i \leq m$: $C[A[i]] = 0$ For $1 \leq i \leq m$: $C[B[i]] = 1$ Initialize answer to $0$ For $1 \leq i \leq m$: If $C[A[i]] = 1$ then $C[A[i]] = 2$ and increment answer Return answer

Top 50 recent answers are included