Questions tagged [arrays]

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

Filter by
Sorted by
Tagged with
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
1answer
700 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 - ...
5
votes
4answers
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, ...
5
votes
1answer
512 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
3answers
6k views

How do I find the max and min value of an array in 3n/2−2 comparisons?

So I'm using this method to find the min and max value of an array simultaneously where I split the array into n/2 and n/2 parts. I then keep splitting each part until I have either a pair of numbers ...
5
votes
1answer
164 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
730 views

Lower bound for sorting n arrays of size k each

Given $n$ arrays of size $k$ each, we want to show that at least $\Omega(nk \log k)$ comparisons are needed to sort all arrays (indepentent of each other). My proof is a simple modification of the ...
5
votes
2answers
1k views

Search for minimum in an array of $k$ monotonic subarrays

Let $A$ be an array of totally ordered elements. A subarray $A[i..j]$ is decreasing if $A[k]\geq A[k+1]$ for all $i \leq k < j$. It is increasing if $A[k]\leq A[k+1]$ for all $i \leq k < j$. It ...
5
votes
1answer
116 views

Finding a small element in a changing array

Consider having an integer array $A$ with $n$ elements, in addition to any data structure you like. The array is initialized to zeros. The goal to to support two operations: ...
5
votes
1answer
81 views

Does the concept of the array pre-date physical computer memory implementations?

Does the concept of the array (a sequence of equally-sized elements accessible in O(1) time, occupying O(n) space) pre-date physical computer memory implementations? I am trying to gauge whether ...
5
votes
2answers
4k views

Finding a O(n) solution to: max difference of pairs array question [closed]

I don't know an O(n) solution to the following: Given an array of n integers, find the largest difference between any two pairs in the array: however, the larger integer must have a higher index in ...
5
votes
1answer
457 views

array median transformation using the min number of steps

Let $A[1...N]$ be an Array of size $N$ with maximum element $\max$. I want to transform array $A$ such that after transformations all elements of $A$ contain $\max$, i.e. after transformation $A = [\...
5
votes
1answer
685 views

Find amortized cost for insertion in binary arrays using accounting/potential methods?

Background: The idea of this data structure is as follows. We will have a collection of arrays, where array $i$ has size $2^i$. Each array is either empty or full, and each is in sorted order. ...
5
votes
1answer
271 views

Why is memory one dimensional?

Addresses in system programming languages like C are one dimensional (i.e. one number). This forces the programmer to make a decision whether matrices are stored "row major" or "column major" causing ...
5
votes
1answer
7k views

Merge two sorted arrays without using additional memory

We have two sorted arrays of integers. Without using additional memory we need to merge these two arrays such that the smallest numbers are in the 1st array and the remaining numbers are in the ...
4
votes
1answer
596 views

Matrix Max in less than O(n)

I am attempting to find the maximum value in a matrix (or 2d array) and want to find it in less than O(n) time. The easiest way, which results in O(n) run time, is an element wise search. If a better ...
4
votes
3answers
589 views

Why shuffling by picking random position in all array instead of a part is not correct

There is a famous problem to generate a random permutation of elements in an array - it's called shuffling. My understanding of that problem is that I have to put every element in an array into a ...
4
votes
2answers
713 views

What is “Oracle Access”?

I'm reading a paper for school and I have come across a passage that I don't understand. It says "If we allow the query to access the entries of the array through an oracle, it is possible to obtain a ...
4
votes
3answers
7k views

Find a weighted median for unsorted array in linear time

For days, I'm trying to figure out, whether it is possible to find an item in array which would be kind of weighted median in linear time. It is very simple to do ...
4
votes
2answers
126 views

Is it better to store the magnitude of an arbitrary-precision number in BigEndian or LittleEndian order in an integer array?

I'm implementing a class which provides arbitrary-precision arithmetic (also called "bignum", "BigInteger", etc.). My questions is about a practical implementation detail: I'm wondering if there is ...
4
votes
2answers
4k views

k-ordered array problem

An array $A[1...n]$ is said to be k-ordered if $$A[i - k] \leq A[i] \leq A[i + k]$$ for all $i$ such that $k < i \leq n - k$. For example, the array $A = [1, 4, 2, 6, 3, 7, 5, 8]$ is 2 ordered. Q1. ...
4
votes
1answer
5k views

Count unique increasing subsequences of length 3 in $O(n\log n)$

Problem: Given an array of $n$ integers, $A[1 \dots n]$, such that any integer occurs at most 2 times in the array, we have to find the number of unique increasing subsequences of length 3 (duplicate ...
4
votes
1answer
324 views

Maximum subarray of bounded length

I'm giving an array $A[0..n-1]$ and an integer $w$. The goal is to find indices $i,j$ that maximize $$\Phi(i,j) = A[i] + A[i+1] + \dots + A[j-1],$$ subject to the requirements that $0 \le i \le j \...
4
votes
1answer
2k views

Efficient way to calculate sum in sliding window?

Assume you have a grid as below: The square is the sliding window. I want to slide this window over all the possible position such that the window is contained in the grid (i.e the edges of the ...
4
votes
1answer
36 views

Randomly filling an $n$-length array with values from $0$ to $k$ that total to $0 < m < nk$ - is a linear-time algorithm possible?

Let $n, k > 0$ and $0 < m < nk$. I want to fill an $n$-length array $A$ with random integer values in the range $[0,k]$ such that $\sum_{i=0}^{n -1} A[i] = m$. Furthermore, all such arrays ...
4
votes
2answers
163 views

Succinct bounded-sum array with $O(1)$ access

Assume we have a $n$ sized integer array $A$, and that we know that $\sum_{i\in[n]}A[i] \le M$. Assume we are using the RAM model with $\Theta(\log n)$ sized memory words (which can be read / written ...
4
votes
1answer
1k views

Lower-bound complexities for finding common elements between two unsorted arrays

I'm facing some problems that deal with finding common elements between unsorted arrays and I'd like to know whether there are well-known lower-bounds for the worst-case and, eventually, what are ...
4
votes
2answers
848 views

What are GPU arrays?

I came across the Python library libgpuarray and was reading about it but could not really understand what a GPU array is and why do we need it? What is the difference between a normal array and GPU ...
4
votes
1answer
55 views

Find two contiguous subarrays with the greatest difference

Here's an interview question I've seen on a few sites. People claim that an O(n) solution is possible, but I've been racking my brain these last 2 days and I couldn'...
4
votes
1answer
78 views

Sorting array with at most two inversions

I have created an algorithm to sort an array of size $n$ with at most 2 inversions with exactly $n$ comparisons in the worst case. I have no idea how to prove that it is optimal in terms of the ...
4
votes
3answers
1k views

How to output all longest decreasing sequences

Suppose I have an array of integers having length $N$. How can I output all longest decreasing sequences? (A subsequence consists of elements of the array that do not have to be consecustive, for ...
4
votes
2answers
119 views

Algorithm to save state of array as it changes

There's an array which changes with every iteration, i.e., an element is added or deleted in every iteration. I have to save the "state" of the array for every iteration, which would later be ...
4
votes
1answer
218 views

Prove correctness of the iterative algorithm

Description: Given an array nums and a value val, remove all instances of that value in-place and return the new length. Do not allocate extra space for another array, you must do this by modifying ...
4
votes
1answer
179 views

Searching a value in a “piecewise” ordered array

If we have an array $A$ of length $N$, which is partitioned into $\sqrt{N}$ adjacent subarrays $A(i)$, each of which is monotonically ordered from $\min(i)$ to $\max(i)$ (it is known what places have ...
4
votes
1answer
101 views

Sort array of duplicate integers in place

Given an array of integers within [1, n] where n = size of array, some elements may appear more than once. Could we sort it with just 1 extra space and in O(n) time?
4
votes
3answers
187 views

Sum of unique elements in all sub-arrays of an array

Given an array $A$, sum the number of unique elements for each sub-array of $A$. If $A = \{1, 2, 1, 3\}$ the desired sum is $18$. Subarrays: ...
4
votes
0answers
1k views

Find the median of two sorted arrays of different size in O(min(log(n),log(m)) complexity

Given two sorted arrays of length m,n, how do I find the median of the union of these two arrays in O(min(log(n),log(m)) time? I've been trying to come up with an algorithm (and a proof) for several ...
4
votes
0answers
687 views

Algorithm for solving rectangle puzzle

Early note: This is not homework. I simply regularly create ideas in an attempt to teach myself a language. For what it's worth I'll be using Javascript for this. That said, I haven't been able to ...
3
votes
3answers
772 views

Runtime of sorting a partially-sorted array

I have an array of $n$ items which is partially sorted like below: $$A[i]\le{A[i+k]}$$ where: $$i=1,2,...,n-k$$ For sorting the array completely, I wonder what the runtime big O is. I feel only ...
3
votes
2answers
74 views

Is it possible to solve this problem in less than n^2 time without using additional space?

Here's the problem: Given an array array containing integers, maximize array[i] + array [j] + |i - j| where i and j both range ...
3
votes
7answers
4k views

Checking if there are 2 elements in an array that sum to X in O(n lg n)

I have thought about the most useful way of checking an array for 2 elements that sum to X. The trivial solution is to check the sum of every element with every element, and the complexity of this ...
3
votes
1answer
119 views

Finding a '1' cell with a '0' to its right in a binary array

Given an array of size n that holds ones and zeros I need to find an index of a 1 cell that has 0 to his right (in then next ...
3
votes
1answer
970 views

what is actually a circular array and representation

There are two ways to implement a circular array either take a new array of size 2N where N is the size of the initial array and copy initial array twice into that ...
3
votes
1answer
290 views

Finding duplicate in immutable array in linear time and constant space

We have a array of $N$+1 integers. The integers range from 1 to $N$. The array contains at least one duplicate. Our goal is to find one of the duplicate entries. We have the constraint that we cannot ...
3
votes
1answer
180 views

Number of Pairs in Array

so hey, I've been recently reading about the Two-Pointer algorithm that allows us to find pairs $(i,j)$ such that $a[i] + a[j] = x$ in $O(m+n)$ instead of the trivial $O(mn)$ time. I was wondering ...
3
votes
2answers
6k views

Row Major vs Column Major order access 2D arrays in programming languages

Programmers prefer accessing a 2D array in Row-Major Order rather than Column-Major Order, Why? Are there some advantages/benefits of accessing a 2D array in row-major as compare to column-major? ...
3
votes
3answers
6k views

Runtime of searching for a number in an array?

Searching for a number in an array is said to have a runtime of O(n) because there may be cases where the number doesn't exist in the array. In such cases, you'd have to have gone through the entire ...
3
votes
2answers
250 views

Sublinear query time for the $i$th element of an array after some additions?

We are given an array $A[1..n]$ of integers, and an array of 3-tuples known as queries. The query tuples $(i,j,v)$ denote additions of an integer $v$ to the subarray of $A[i..j]$. I'm interested in ...
3
votes
4answers
703 views

Get specified bit in addition of two large binary numbers

I am performing an addition operation on two large binary numbers that have an equal number of bits. Both numbers are stored in an array of length $N$, which is rather large. At first I tried running ...

1
2
3 4 5
9