Questions tagged [arrays]
A sequential random-access data structure whose size can typically not be changed after creation.
566
questions
2
votes
0
answers
55
views
Minimizing the sum of differences in a pair [duplicate]
You have two arrays, a and b
Both contain n elements, all positive and distinct.
you have to create a pair, by taking one number from each array, such that the sum of the differences of the pairs ...
1
vote
2
answers
284
views
Amortized time for dynamic array
I'm struggling to understand one part from the book "Cracking the coding interview".
The author states inserting an element in a dynamic array is $O(1)$ most of the time, except when the array is full ...
- 119
2
votes
2
answers
301
views
Finding largest farthest increasing pairs in array?
Is there a simple linear algorithm for finding in an array A two such elements that $A[i] > A[j]$ and $i - j$ is as large as possible? If one wants to actually return the indices, then linear ...
- 221
2
votes
2
answers
172
views
Managing an hotel using AVL trees - Data Structures
I have a Data Structure question where I need to manage an hotel, each room has a number between $1-n$
and it can be occupied or not.
Available Data structures: AVL* Trees, B-Trees, Arrays, Stacks, ...
2
votes
1
answer
1k
views
Algorithm for splitting an array into k sub-arrays
We want implement a data structure that have the following methods: Init(A,k)- Gets an array A with n different values and initialize our data structure that so it will divide A into k equally sized ...
- 241
0
votes
1
answer
414
views
Maximum Circular Subarray sum
This is a question from the book Algorithms by Jeff Erickson.
Suppose A is a circular array. In this setting, a “contiguous subarray” can be either an interval A[i .. j] or a suffix followed by a ...
- 25
1
vote
1
answer
107
views
How to mathematically determine row, column, and sub-square of cell in nxn array where n is a perfect square?
Given an one dimensional array of size nxn, where n is a perfect square
How can one mathematically determine the row, column, and/or sub-square the cell resides in? Additionally, is there a ...
- 113
1
vote
2
answers
181
views
Given a list of integers and a target integer, return the number of triplets whose product is the target integer and two adjacent triplets
Question: Given a list of integers (possibly negative) and a target integer, return the number of triplets whose product is the target integer and two of the triplets must be adjacent.
More ...
- 169
0
votes
1
answer
82
views
Efficient algorithm to compare arrays problem
I was submitted an interesting problem, but I wasn't able to find a solution.
Define a function p(x, y) that takes int x and y, with ...
anon
1
vote
0
answers
43
views
Matrix multiplication over range in $O(n)$
Let $Q$ denote the number of queries.
I have a $25 \times 25$ matrix in each cell of an array of size $n$. Let us denote this array by $A$. It's a special matrix, more specifically, all elements are $...
- 11
2
votes
1
answer
82
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)...
- 23
1
vote
2
answers
180
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 ...
- 279
1
vote
1
answer
168
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:
...
- 296
4
votes
1
answer
383
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'...
- 143
0
votes
3
answers
441
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.
...
0
votes
0
answers
452
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 ...
- 1
1
vote
1
answer
738
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:
...
1
vote
3
answers
2k
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 ...
- 17
5
votes
3
answers
2k
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 ...
- 151
1
vote
1
answer
180
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 ...
1
vote
0
answers
37
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, ...
- 155
1
vote
1
answer
348
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 ...
- 111
2
votes
1
answer
236
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 ...
1
vote
1
answer
733
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,...
- 11
0
votes
4
answers
228
views
$ \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 ...
- 101
2
votes
1
answer
277
views
Minimum moves to "stabilize" an array
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 ...
- 1,428
2
votes
1
answer
66
views
What algorithms for unification over (multidimensional) array terms?
I am looking for references on implementing unification over multidimensional array terms.
Are there specialized unification algorithms for those cases? I wasn't able to find satisfactory literature ...
- 205
0
votes
1
answer
747
views
pseudocode to split number value to array of numbers
How to write a pseudocode to split a number value to array of numbers? Let's say the number value is 12345. I need to convert it into [1,2,3,4,5].
- 103
1
vote
1
answer
4k
views
Time complexity of removing duplicates in lists
Question
I am wondering what is the minimum time complexity of get the unique value of a array in two conditions: keep the order or not.
For example, suppose we have a original array ...
- 121
5
votes
1
answer
1k
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 - ...
- 155
-1
votes
1
answer
2k
views
Minimum number of cans needed to carry all used water
so I've just attempted an online technical test. It was on hacker rank however I'm sure leetcode usually has the same (and more) so thought i'd ask.
I could not think of a nice solution and cannot ...
- 11
1
vote
0
answers
298
views
finding the parent index in an interval heap (stored on an array) given a child index
an interval heap is a binary tree stored on an array where the size of each node is 2.
i would like to be able to find the index of a parent and find one of the child indices given the index of a ...
- 11
1
vote
1
answer
183
views
Find number of triples that sum up to zero in query-intervals
My problem is that we have an array of $N$ integers $(N <=5000)$ on the interval $[-10^6,10^6]$. We also have $Q$ queries $(Q <= 10^5)$ giving us some range in the array.
For each query, we ...
- 29
0
votes
0
answers
28
views
Maximising sum of associated elements
I have a set of elements. Each element is connected with every other element by a path of length $l_i,_j\geq0$ (where i$\neq$j).
I have to calculate the maximum sum of path length such that I should ...
- 1
1
vote
2
answers
569
views
Sorting a large list of test scores
You have a large list (say N > 10000) of test scores which you would like to sort. The test scores are between 1 and 100. What is quickest way to sort the list?
First thought. We have a O(N log N) ...
- 143
1
vote
0
answers
23
views
When was the dynamic array first introduced as an example for amortized analysis?
I'm writing a report on amortized analysis, and I'm using the example of a dynamic array to explain each method. I think it would be nice to add a reference to when this example was first used, as it ...
- 11
0
votes
1
answer
165
views
Which sort algorithm to choose given two specific arrays?
Interview question:
Given array A which contains only odd numbers and array B which contains only even numbers, explain
which sort algorithm would you choose.
I said merge sort. I thought that ...
- 3
1
vote
1
answer
2k
views
Selecting elements from two arrays to get a target sum
Let $A$ and $B$ be two arrays of size $n$ with positive integer values. Let $k$ be a given positive integer.
Design an algorithm to solve the following problem.
For each index $i$ ($1\leq i \leq n$)...
- 367
4
votes
1
answer
157
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?
- 151
1
vote
0
answers
44
views
Find a non-minimal sequence of elements covering the support set
Consider a sequence $s$ of $n$ integers (let's ignore the specifics of their representation and just suppose we can read, write and compare them in $O(1)$ time with arbitrary positions). Denote $\text{...
- 965
0
votes
2
answers
933
views
Given an array arr[] of N integers. Do the following operation n-1 times
For every Kth operation:
Right rotate the array clockwise by 1.
Delete the (n-k+1)th last element.
eg:
A = {1, 2, 3, 4, 5, 6}. Rotate the array clockwise i.e. after rotation the array A = {6, 1, 2, ...
- 163
2
votes
1
answer
454
views
Space-efficent storage of a trie as array of integers
I'm trying to efficiently store a list of strings in an array with the following constraints:
All strings consist of 8-bit characters (0..255).
The final trie is static, i.e. once it is built, no ...
- 360
0
votes
0
answers
43
views
What constitutes a minimal-sum section of an integer array
I'm having trouble understanding what constitutes a "minimal sum section" of an integer array. My book defines it as the following:
Let $a[0],\dots, a[n-1]$ be the integer values of an array $a$.
...
- 157
3
votes
1
answer
116
views
Improve algorithmic complexity
We have an array of N size. We have to perform Q queries on it, in which each Query contains and Index I for which we do:
...
- 31
7
votes
3
answers
1k
views
Recover an array from its insertion indices
An array is built starting with an empty array, and then a sequence of insertions:
insert $a_1$ at index $z_1=1$
insert $a_2$ at index $z_2$
insert $a_3$ at index $z_3$
...
and so on. When we ...
- 499
1
vote
0
answers
33
views
Intersection of 2 arrays
Here is a question i came across :
Given two arrays, write a function to compute their intersection.Here we will allow the duplicates.
Note:
Each element in the result should appear as many ...
- 159
3
votes
1
answer
112
views
Are all data structures in the von Neumann architecture based on the array, or array-like?
I am an old Pythonista now learning C and how various data structures and types are implemented, such as binary trees and hash tables. Learning about the latter, leads me understand that the hash ...
- 131
1
vote
2
answers
399
views
Efficient algorithm for finding optimal sum from both arrays
I have two arrays(A,B) and a sum M. I need to find one number from each array that makes the sum M. If there is no two elements that form sum M, then nearest and less than M sum is the solution. See ...
- 113
2
votes
3
answers
267
views
Remove x last elements of an array and reinsert them before position y
I am looking for an algorithm to move a subarray in before an element (which is not part of that subarray) in the same array where the last element of the subarray is the last element of the array ...
- 65
1
vote
1
answer
330
views
Return the subset with smallest cardinality of an array whose elements sum to at least a given value
Suppose we are given an array $A[1\ldots n]$ and a value $C$.
Is there an algorithm with linear expected runtime that can produce an array that is the subset with smallest cardinality of $A[1\ldots ...
- 43