# Questions tagged [arrays]

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

392 questions
Filter by
Sorted by
Tagged with
11k views

568 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 ...
414 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 ...
146 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 ...
632 views

### How can merging two sorted arrays of N items require at least 2N - 1 comparisons in every case?

The HW question, on page 362 of Data Structures and Algorithms in C++: Fourth Editionby Mark Allen Weiss, reads as follows: Prove that merging two sorted arrays of N items requires at least 2 * N - ...
8k 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, ...
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-...