# Questions tagged [arrays]

A sequential random-access data structure whose size can typically not be changed after creation.

428 questions
Filter by
Sorted by
Tagged with
540 views

### Find the kth smallest element in an unsorted array of non-negative integers

I need to find the kth smallest element in an unsorted array of non-negative integer. kth smallest element is the minimum possible n such that there are at least kth elements <= n. The rub here ...
8k views

### How to prove that average complexity is N/2 for linear search in the unsorted array [duplicate]

All tutorials on algorithms show the complexity for the linear search in the unsorted array in the average case as N/2. I understand that the average case means the ...
60 views

### Why is subarray $A[p..k-1]$ empty when $k=p$?

I'm working through a proof of correctness for merge sort. I'm given a loop invariant for a for loop, which makes reference to a subarray $A[p..k-1]$. During the initialization step of the ...
455 views

### Maximum number of segments with no intersection [duplicate]

This is an interview question. Suppose you have an array of n segments, when each segment is a pair of two integers: start point and end point. For example: ...
420 views

### Sort an array based on dependencies

I have an array of objects, each of them has a numeric id and another array attached to them. The array in the object contains the dependencies of that object. Each dependency is an id from the other ...
174 views

### Find the smallest element greater than current element

my question is that given a list of integers (lets say A), for each element A[i], find the smallest element A[j] which could satisfy A[i] < A[j] and i < j. Return -1 if there is no such element. ...
150 views

### Proving an algorithm wrong

So I have this algorithm that outputs the largest value of an array: Input: $A[1,\dots,n]$, $n\geq 1$ Output: Largest value of an array ...
717 views

### Representing non-contiguous memory regions as a standard vector with O(1) access

What interesting alternatives are there for constructing an arbitrarily large static array from smaller scattered blocks of fixed-sized non-contiguous blocks of memory? This is similar to the ...
92 views

### How to sort a large list of elements where everything is sorted but k elements?

Assuming the list is very large, and $k$ is very small, what's the fastest algorithm to sort this list?
75 views

If you implement a stack with a dynamic array-based with LinkedList you need more memory than with a dynamic array, and with dynamic array for insert in amortized cost is O(1), so the advantage of the ...
34 views

### Finding maximum takes at least $\lceil n/2 \rceil$ comparisons

We are given an array $A$ with $n$ elements, $n \in \mathbb{N}$ and all elements are in the set $\{1,2,3, \cdots, n \}$. I want to prove that finding the maximum in $A$ (that is, outputting the index ...
68 views

### Using bit arrays to solve crossword puzzles

I have read Crossword Puzzles and Constraint Satisfaction by Connor, Duchi and Lo and I am trying to implement this variation of crossword solving algorithm. I can't understand the bit array data ...