# Questions tagged [arrays]

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

356 questions
Filter by
Sorted by
Tagged with
3answers
11k views

1answer
524 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 ...
1answer
288 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 ...
1answer
142 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 ...
5answers
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 ...
4answers
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, ...
1answer
457 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 ...
2answers
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-...
1answer
161 views

### A vector-like data structure with allocation table; O(1) indexing time required

I am a beginner in data structures and recently came across a vector implemented on an array, which is extended on demand. Of course the table cannot be extended "in place", we must allocate a new ...
1answer
17k views

### What is a contiguous subarray?

What is a contiguous subarray? I have tried searching online and have found pages about solving the largest contiguous subarray problem but none with a definition or explanation of what contiguous in ...