# Questions tagged [arrays]

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

441 questions
Filter by
Sorted by
Tagged with
22 views

### Running time of RandomQuickSort when i/p Array A is uniformly randomly permuted before QuickSort begins

Suppose the input array A is uniformly randomly permuted before QuickSort begins. Does the same expected runtime hold as for the RandomQuickSort? Why or why not? So RandomQuickSort is based on ...
43 views

### A silly doubt on Computer Science Objects: Arrays, Lists, Strings, and Vectors, are they the same concept?

First of all I'm a Physics Student and I've been arguing with my brother concerning the usage and the fundamental meaning of a vector on Computer Science (CS). I) Vectors A vector have a axiomatic ...
28 views

30 views

### Why does a range query on a segment tree return at most $\lceil \log_2{N} \rceil$ nodes?

If an array $A[1 \ldots N]$ is represented using a segment tree having sets in each interval, why does a range query $[L\ldots R]$ returns at most $\lceil \log_2{N} \rceil$ sets (or disjoint intervals)...
37 views

### Find combination of vectors from array that sum up to s

I have an array of $n$ $m$-dimensional vectors (in my case, they're 27 dimensional). I also have an $m$-dimensional vector $s$. I want to find all combinations of $k$ vectors from my array whose ...
30 views

### Longest subarray with at most two different values - Runtime complexity for a DP solution

Consider the problem of finding, for a given input array, the longest subarray with at most two different values. For example: ...
59 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'...
86 views

### Formal definition of the Dynamic Array - what is the Dynamic Array

I've researched quite a bit about this topic. Since I'm kind of a fan of Exact Sciences, I love everything to have a crystal-clear and determined definition, without any ambiguous or dubious points. ...
30 views

### Options for approaching stable marriage problem with unequally sized sets of elements/preferences

I am looking for an algorithm/code that will provide stable matching for two unequally sized sets of elements (clubs and students) with an unequal set of preferences. There is a large pool of students ...
81 views

### Generate all combinations of a set/array with specific conditions

Apologies if this isn't posted in the right stack exchange, but I'm trying to come up with an algorithm that generates a set of sets ('set' as synonymous with 'array') with the following conditions: ...
115 views

### Can you insert into sorted list with time O(1)?

Wondering if this was possible. If I have a sorted list, can I find the right spot for an integer and insert it, all in O(1) time? The only way I can think to do this is via having a MASSIVE hashmap ...
489 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 ...
52 views

### How to shift a matrix by x rows and y columns in the most efficient way?

My objective is to shift rows by x and columns by y in a 2d matrix. My problem is to solve this objective in an efficient manner. x and y could be negative or positive. Negative would mean up/left ...
13 views

### Minimising total access time to elements in an array which is accessed sequentially

Starting with two examples: for(i = 1; i<10; i++) {B[i] = 0;} for(i = 1; i<10; i++) {B[2i] = 0;} In the first example, ...
45 views

### Is it possible to find a supersequence of a single array?

In Jeff Erickson's Algorithms textbook, the chapter on Dynamic Programming asks you to "Describe an efficient algorithm to compute the length of the shortest oscillating supersequence of an arbitrary ...
42 views

### Finding largest sum of $k$ elements below threshold

I was working on a project and am stuck in the middle unable to find an optimal method to solve this problem. Consider an array $A$ of $n$ elements. I have to choose $k$ elements such that the sum of ...
30 views

### Reverse of In-place algorithm for interleaving an array

How to do the reverse process of In-place algorithm for interleaving an array question?
132 views

### Array segmenting algorithm

I have a sorted array of integers [x, ..., n, ..., y] so that x > 0 n - x = random positive integer The array might look something like this: [1, 2, 3, 15, 16, 17, 120, 121, 122, 123, 124, 125, 126,...
### $\Omega(m)$ and $O(m)$ meaning in theorem proof about dynamic array complexity
My algorithms and data structures' book states that to create a dynamic array the following procedure is followed: Let $d$ be the length of an array $a$ and $n$ the number of elements stored in ...
We have given an array of size $N$, consisting of positive integers, and an integer $H$. We also know that an array is stable iff $|A_i - A_{i-1}| \leq H$ for each $1<i<N-1$. We can modify the ...