# Questions tagged [arrays]

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

345 questions
Filter by
Sorted by
Tagged with
10k views

514 views

### How do arrays work “under the hood”?

In some languages (such as C), arrays seem very simple to me. When allocating memory for these, all you need to do is pick a starting point in memory and then allocate the next ...
271 views

### Find pairs of integers (a, b) in an array such that a = b + k in linear time - elements are not unique

A while ago, I was asked to solve a question similar to this: We are given an array arr and we would like to find all pairs of items ...
139 views

### Sort 2D arrays so that cost of reaching new position as described at each iteration is minimized

Problem is as following: We are 8 trumpet players in an orchestra. There are for example 4 parts so there are always two players on the same part. Now, there are not always the same two players ...
3k views

### What is the best solution to find whether the sum of an array is even or odd

I was asked this question in an interview. I was not able to find a better solution than $O(n)$ which is just going over the array and finding the sum. Can it be done any better? I am not really ...
7k views

### What is the advantage of heaps over sorted arrays?

I'm fairly new to heaps and am trying to wrap my head around why min and max heaps are represented as trees when a sorted array appears to both provide min / max properties by default. And a follow ...
7k views

### Find maximum element in sorted arrays in logarithmic time

Been stuck on this for a while, would really appreciate some help: Suppose you are given an array A[1...n] of sorted integers that has been circularly shifted k positions to the right. For example, ...
451 views

### From Guido's essays, how does this function avoid quadratic behavior in a string concatenation algorithm?

I am reading one of Guido van Rossum's essays on optimization in Python. We are interested in converting a Python list of integers to their character equivalents. Here's the straightforward ...
4k views

### Proving the Bubblesort actually sorts

Say $A'$ is the output of $\mathrm{Bubblesort}(A)$ on an array of length $N$. To prove that Bubblesort works, we have to prove that it always terminates and that A'\leq A' \leq \dots \leq A'[N-...