Questions tagged [arrays]

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

Filter by
Sorted by
Tagged with
62
votes
3answers
11k views

In-place algorithm for interleaving an array

You are given an array of $2n$ elements $$a_1, a_2, \dots, a_n, b_1, b_2, \dots b_n$$ The task is to interleave the array, using an in-place algorithm such that the resulting array looks like $$...
49
votes
6answers
10k views

Keeping a String Secret in (Open) Source Code

I have finished developing an app for Android and intend to publish it with GPL -- I want it to be open source. However, the nature of the application (a game) is that it asks riddles and has the ...
32
votes
4answers
3k views

How to measure “sortedness”

I'm wondering if there is a standard way of measuring the "sortedness" of an array? Would an array which has the median number of possible inversions be considered maximally unsorted? By that I mean ...
30
votes
5answers
45k views

Adding elements to a sorted array

What would be the fastest way of doing this (from an algorithmic perspective, as well as a practical matter)? I was thinking something along the following lines. I could add to the end of an array ...
21
votes
7answers
7k views

One element that differs in two arrays. How to find it efficiently?

I am preparing for a coding interview and I can't really figure out the most efficient way to solve this problem. Let's say we have two arrays consisting of numbers that are unsorted. Array 2 ...
20
votes
3answers
2k views

Is there an algorithm which finds sorted subsequences of size three in $O(n)$ time?

I want to prove or disprove the existence of an algorithm which, given an array $A$ of integers, finds three indices $i, j$ and $k$ such that $i < j < k$ and $A[i] < A[j] < A[k]$ (or finds ...
19
votes
1answer
4k views

Is there an existing data structure that is of fixed size, and will push the oldest/last element out if a new element is inserted?

I'm looking for a data structure that will push its oldest/last element out if a new element is inserted. For example, let D represent the structure. ...
18
votes
1answer
899 views

Saving on array initialization

I recently read that it is possible to have arrays which need not be initialized, i.e. it is possible to use them without having to spend any time trying to set each member to the default value. i.e. ...
16
votes
3answers
2k views

Largest sum divisible by n

I asked this question on StackOverflow, but I think here is a more appropriate place. This is a problem from Introduction to algorithms course: You have an array $a$ with $n$ positive integers (...
15
votes
9answers
3k views

How to find 5 repeated values in O(n) time?

Suppose you have an array of size $n \geq 6$ containing integers from $1$ to $n − 5$, inclusive, with exactly five repeated. I need to propose an algorithm that can find the repeated numbers in $O(n)$ ...
15
votes
6answers
9k views

How to implement two stacks in one array?

I want to begin by saying that this is NOT a homework question. I am reading Introduction to Algorithms - the famous CLRS text to become a better programmer. I am trying to solve the problems and ...
14
votes
1answer
2k views

Counting inversion pairs

A classic application of divide and conquer is to solve the following problem: Given an array $a[1\dots n]$ of distinct, comparable elements, count the number of inversion pairs in the array: pairs $(...
13
votes
1answer
472 views

Overflow safe summation

Suppose I am given $n$ fixed width integers (i.e. they fit in a register of width $w$), $a_1, a_2, \dots a_n$ such that their sum $a_1 + a_2 + \dots + a_n = S$ also fits in a register of width $w$. ...
12
votes
6answers
16k views

Why do negative array indices make sense?

I have came across a weird experience in C programming. Consider this code: ...
12
votes
3answers
8k views

Finding the element that occurs the most in a very large file

I've heard this interview question asked a lot and I was hoping to get some opinions on what good answers might be: You have a large file 10+ GB and you want to find out which element occurs the most, ...
12
votes
1answer
2k views

Counting number of sums from contiguous subarrays of an array

We are given an array $a[1 \ldots n]$ with all $a[i]>0$. Now we need to find how many distinct sums can be formed from its subarrays (where a subarray is a contiguous range of the array, i.e., $a[...
11
votes
2answers
1k views

How to deal with arrays during Hoare-style correctness proofs

In the discussion around this question, Gilles mentions correctly that any correctness proof of an algorithm that uses arrays has to prove that there are no out-of-bounds array accesses; depending on ...
11
votes
1answer
418 views

Preprocess an array for counting an element in a slice (reduction to RMQ?)

Given an array $a_1,\ldots,a_n$ of natural numbers $\leq k$, where $k$ is a constant, I want to answer in $O(1)$ queries of the form: "how many times does $m$ appear in the array between indices $i$ ...
10
votes
2answers
143 views

Name of this rearranging/sorting problem?

You are given an array of length $n$. Each element of the array belongs to one of $K$ classes. You are supposed to rearrange the array using minimum number of swap operations so that all elements from ...
10
votes
0answers
219 views

Is there a data-structure which is more efficient than both arrays and linked lists? [duplicate]

Background: In this question we care only about worst-case running-time. Array and (doubly) linked lists can be used to keep a list of items and implement the vector abstract data type. Consider the ...
9
votes
3answers
1k views

Finding number of smaller elements for each element in an array efficiently

I am stuck on this problem: Given an array $A$ of the first $n$ natural numbers randomly permuted, an array $B$ is constructed, such that $B(k)$ is the number of elements from $A(1)$ to $A(k-1)...
8
votes
2answers
2k views

Algorithm to find smallest difference in array

We want an algorithm that, given an array of length $n$ of integers, find the minimum difference between two integers in the array. One such algorithm is to sort the array and check adjacent pairs of ...
8
votes
1answer
219 views

Find subsequence of maximal length simultaneously satisfying two ordering constraints

We are given a set $F=\{f_1, f_2, f_3, …, f_N\}$ of $N$ Fruits. Each Fruit has price $P_i$ and vitamin content $V_i$; we associated fruit $f_i$ with the ordered pair $(P_i, V_i)$. Now we have to ...
8
votes
2answers
539 views

Detecting overflow in summation

Suppose I am given an array of $n$ fixed width integers (i.e. they fit in a register of width $w$), $a_1, a_2, \dots a_n$. I want to compute the sum $S = a_1 + \ldots + a_n$ on a machine with 2's ...
7
votes
6answers
4k views

C++ Strings vs. Character Arrays

Why do you think it is that most C++ instructors teaching college level computer sciences discourage or even forbid using strings for text, instead requiring students to use character arrays? I am ...
7
votes
2answers
482 views

Find a point shared by maximum segments

Given: $N$ segments (arrays) of ordered integers, integers could be from $-K$ to $K$. Example: ...
7
votes
1answer
465 views

Applicative-order languages don't support constant time array writes? If not, why not?

I'm reading Steven Skiena's "The Algorithm Design Manual", and in one of his War Stories on page 155 he states: Efficiency is a great challenge in Mathematica, due to its applicative model of ...
7
votes
3answers
275 views

Are compilers able to detect alternating accesses to arrays and interleave them in memory?

Is it possible to design a compiler which optimizes a loop in which arrays are accessed in alternate fashion? For example like this: ...
7
votes
0answers
423 views

What is the average-case running time of Fun-sort?

I read this paper: http://www.sciencedirect.com/science/article/pii/S0166218X04001131?np=y (you can check the PDF online for free), and I translated section 4's Fun-sort algorithm (correct me if I'm ...
6
votes
3answers
815 views

What piece am I missing to turn this idea into a programming language?

I've been doing some reading (I'll name drop along the way) and have selected a few scattered ideas that I think could be cobbled together into a nifty esoteric programming language. But I'm having ...
6
votes
2answers
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 ...
6
votes
2answers
617 views

Complexity of algorithm to find number of elements > element index i in an array

The question is: Given an array of size N, arr, create another array whose index i = number of elements in sub-array(arr, i+1, N-1) that are greater than arr[i]. Eg. if input array is, 5 3 9 8 2 6 ...
6
votes
1answer
4k views

Why does merging two sorted arrays take 2N - 1 comparisons?

A friend of mine asked me a question on how to prove that merging two sorted arrays requires at least 2N - 1 comparisons Prove that merging two sorted arrays of N items requires at least 2N-1 ...
6
votes
1answer
2k views

What is a partially sorted array?

I come across this definition but it's not so clear for me ! An array is partially sorted if the number of inversions is less or equal a constant times the array length. if array length is N then ...
6
votes
3answers
7k views

Number of submatrices with a particular sum

Given a $n\times n$ matrix A[0...n-1][0....n-1] where all entries are non-negative integers, and a non-negative integer K, I ...
6
votes
2answers
197 views

Transforming an array into one with descending order

Problem Description Given an array $A$ of $n$ integers, find the minimum number of operations to turn it into a new array $\widehat{A}$ with a (weakly) descending order: we require that $\hat{a}_i \...
6
votes
3answers
3k views

Algorithm with $O(n)$ time and $O(n)$ space to compare two arrays

$A$ and $B$ are two arrays with $n$ elements each in the range $1$ to $n^2$. 1.How to check if the elements of $A$ are distinct in $O(n)$ time and $O(n)$ space 2.How to check if $A$ and $B$ have a ...
6
votes
1answer
2k views

Maximum number of inversions that can be removed by swapping two elements?

I have come across a question that is a bit hard to understand due to its wording, I may havecome up with a possible solution, but I don't know if it's correct. Can you please help me? Thanks in ...
6
votes
3answers
8k views

Algorithm to find the mode in a unimodal array

I am given the following problem in an Algorithms class: Assume that you are given an array A[1 . . . n] of distinct numbers. You are told that the sequence of numbers in the array is unimodal, ...
6
votes
4answers
3k views

Finding the Largest “Ordered” Difference in Elements of an Array

Suppose we are given an array of positive integers $P = [p_1, p_2, \dots, p_N]$ where each $p_i$ represents the price of a product on a different day $i = 1 \dots N$. I would like to design an ...
6
votes
1answer
264 views

Sum of all products of subarrays

For any three-dimensional array $A$ of size $n_1 \times n_2 \times n_3$ let $P(A)$ be the product of all its elements, i.e. $$P(A) = \prod_{i_1 = 1}^{n_1} \prod_{i_2 = 1}^{n_2} \prod_{i_3 = 1}^{n_3} ...
6
votes
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 ...
6
votes
1answer
291 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 ...
6
votes
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 ...
5
votes
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 ...
5
votes
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, ...
5
votes
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 ...
5
votes
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'[0]\leq A'[1] \leq \dots \leq A'[N-...
5
votes
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 ...
5
votes
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 ...