Questions tagged [arrays]
A sequential random-access data structure whose size can typically not be changed after creation.
441
questions
-2
votes
1answer
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 ...
1
vote
2answers
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 ...
2
votes
2answers
28 views
Finding the most frequent element assuming $\Theta(n)$ frequency
We know [Ben-Or 1983] that deciding whether all elements in an array are distinct requires $\Theta(n \log(n))$ time; and this problem reduces to finding the most frequent element, so it takes $\Theta(...
1
vote
1answer
22 views
Count minimum number of steps to destroy all blocks
Given a sequence of integers $A_x$ of length $n$ such that $1 \leq A_x \leq N$,in one step we can remove an element, but when we remove an element we also delete all adjacent numbers which have the ...
-3
votes
1answer
49 views
Subset sum problem with a complication
I have a sorted list of numbers. I know they can be divided into two parts. I also know the sum of those 2 parts. I want to know what these subsets are. How can i find them?
The size of my list can be ...
-1
votes
1answer
36 views
Finding which value I will be on after a certain number of steps
I have a fixed array: [a,b,c], I wanna loop through this 3-items-sized array for 7 times in order to find what I would get at that exact step.
The "value stack&...
2
votes
0answers
46 views
How to parallelize a summation efficiently
Say I have an array a[1..n], and I want to output an array s[1..n] with s[i] = a[1]+...+a[i]. What is the best (or at least standard) way to do so in parallel?
The way I can think of doing it, given m ...
1
vote
2answers
125 views
Find the length of the longest subarray having sum greater than k
I tried to solve this problem but could not do it better than $O(n^2)$.
My Algorithm:
...
1
vote
0answers
14 views
N-dimensional generalization of map and reduce?
Is there any conceptual generalization of higher-order functions like map and reduce but for N-dimensional objects (e.g. arrays or tensors)?
For mapping, I guess it would be a point-wise ...
-1
votes
1answer
56 views
What is Simple Uniform Hashing, and why searching a hashtable has complexity Ī(n) in the worst case
Can anyone explain nicely what Simple Uniform Hashing is, and why searching a hashtable has complexity Ī(n) in the worst case if we donāt have uniform hashing (where n is the number of elements in the ...
1
vote
0answers
44 views
Algorithm for summation with lowest maximum temporary sum
I've got this problem on my last exam, which I struggle to deal with.
Let's say we have array of $N$ integers (it can be float too, but let's say integers for sake of simplicity. We need to sum those ...
0
votes
0answers
41 views
Why do we need MinHeap for Meeting Rooms 2 Leetcode problem
I came across this problem online which is a Leetcode premium problem. Most of the people are solving this using Minheap. To me using minHeap for this seems like repetitive way to solve a problem if ...
0
votes
0answers
34 views
Reconstructing an Array via Time-Intensive Subset Queries
I am trying to design an algorithm for a problem, and the following is an auxiliary problem for which a good solution would imply a faster algorithm for the original problem.
I am given access to an ...
-2
votes
1answer
114 views
How to calculate the minimum price required to buy all the stones?
I have shared the question above. My current algorithm does the calculation in O((n^4)*(2^n)).
Can someone please help me out to solve this faster?
3
votes
1answer
65 views
$\Phi_1=1$ or $\Phi_1=2$ for the dynamic $\text{Table-Insert}$ , where $\Phi_i$ is the potential function after $i$ th operation, as per CLRS
The following comes from section Dynamic Tables, Introduction to Algorithms by Cormen. et. al.
In the following pseudocode, we assume that $T$ is an object representing the table. The field $table[T]$...
0
votes
0answers
40 views
Which advanced data structure to use?
For range queries on a subarray [L,R] , I want to find all the indices of successive maximums from left to right within O(log(R-L+1)), excluding index "L". I know using segment trees I can ...
1
vote
1answer
44 views
How to find the size of gaps between entries in an array so that the first and last element of the array is filled and the gaps are all of equal size?
I have an array a of n entries. I need to place a token on the first and last position of that array, so a[0] = 1 and a[n-1] = 1....
2
votes
1answer
71 views
Returning random integer from interval based on last result and a seed
Suppose we have an interval of integers [a, b]. I would like to have a function that returns random members from within the interval, without repetitions. Once that all members within the interval are ...
2
votes
1answer
36 views
How do you find all integers in a sorted array of size n that appear n/k times?
I try to find the solution to this problem:
How do you find all integers in a sorted array of size n that appear n/k times in less than O(klogn) time?
I could only find this question, where O(klogn) ...
2
votes
1answer
44 views
Smallest subarray problem
Say you have an array of integers like [1, 2, 3, 4, 5, 6], the problem is to find the smallest way to break up the array into sub-arrays where each sub-array satisfies the following requirement:
sub-...
1
vote
1answer
35 views
Find position in array where element-wise multiplication with string of 1 and 0s results in max value
I have a sequence of 1s and 0s. For example: $bits = [1, 0, 1, 1, 1, 0]$. I also have an array of positive integers. For example $arr = [12, 23, 4, 6, 8, 0, 24, 72]$. I need to find the index, $i$, in ...
0
votes
0answers
15 views
How to pick a random index in an array based on the index's value?
While solving a problem on leetcode, I used a heap to give the largest probable value. The problem statement is as follows:
Given an array w of positive integers, where w[i] describes the weight of ...
3
votes
0answers
45 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
2answers
47 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 ...
0
votes
0answers
40 views
Choosing potential function in amortized analysis of the dynamic array
Suppose we have a dynamic array with some initial capacity $c_{initial}$ (i.e., the dynamic array with zero elements will have this capacity). The $add$ operation is modified the following way:
New ...
2
votes
2answers
50 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 ...
2
votes
2answers
85 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
1answer
54 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 ...
0
votes
1answer
36 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 ...
1
vote
1answer
34 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 ...
1
vote
2answers
35 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 ...
0
votes
1answer
42 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 ...
1
vote
0answers
33 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 $...
1
vote
1answer
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)...
1
vote
2answers
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 ...
1
vote
1answer
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:
...
4
votes
1answer
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'...
0
votes
3answers
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.
...
0
votes
0answers
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 ...
1
vote
1answer
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:
...
1
vote
3answers
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 ...
5
votes
1answer
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 ...
1
vote
1answer
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 ...
1
vote
0answers
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, ...
1
vote
1answer
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 ...
2
votes
1answer
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 ...
0
votes
0answers
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?
1
vote
1answer
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,...
0
votes
1answer
50 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 ...
2
votes
1answer
38 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 ...
