New answers tagged arrays
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
