New answers tagged

0

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.


3

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


2

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 ...


1

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 ...


1

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 ...


1

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(...


0

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) ...


0

There are two famous problems that are similar to what you're looking for. Yours comes closest to the subset sum problem https://en.wikipedia.org/wiki/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....


4

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