Questions tagged [arrays]
A sequential random-access data structure whose size can typically not be changed after creation.
404
questions
1
vote
1answer
30 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:
...
0
votes
2answers
43 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 ...
3
votes
1answer
46 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 ...
0
votes
0answers
16 views
What are some unusual or creative implementations of ADTs you've seen?
While learning about ADTs in a data structures course, we learned that the List ADT is most commonly implemented using linked nodes or arrays. Are there any other fundamentally different and unusual ...
0
votes
1answer
41 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
10 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
26 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
37 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
23 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
60 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
42 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
29 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
vote
1answer
39 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 ...
0
votes
1answer
33 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].
-1
votes
1answer
77 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 ...
5
votes
2answers
642 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 - ...
-1
votes
1answer
569 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 ...
1
vote
0answers
47 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 ...
1
vote
1answer
72 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 ...
0
votes
0answers
52 views
Selection Sort vs Merge Sort
I recently wrote a written test for the recruitment of Scientists/Engineers in ISRO(Indian Space Research Organization) few days back and the following question appeared in the test.
Of the following ...
0
votes
0answers
25 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
vote
2answers
276 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) ...
1
vote
0answers
13 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 ...
0
votes
1answer
111 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 ...
1
vote
1answer
154 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$)...
4
votes
1answer
95 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?
2
votes
0answers
38 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{...
0
votes
1answer
103 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, ...
2
votes
1answer
53 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 ...
0
votes
0answers
37 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$.
...
3
votes
1answer
49 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:
...
6
votes
3answers
367 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 ...
1
vote
0answers
23 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 ...
3
votes
1answer
47 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 ...
1
vote
2answers
78 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 ...
2
votes
3answers
255 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 ...
1
vote
1answer
81 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 ...
3
votes
1answer
53 views
How to answer multiple queries efficiently?
I am given a $N$-length integer array. For each integer, I am given 4 values:
$$[\mathit{left},\mathit{right},t,\mathit{value}]$$
$$1\leq \mathit{left},\mathit{right},t\leq N$$
For each query, I ...
2
votes
2answers
274 views
Maximum number of multiples of an array element preceding it
Given an array of size $n$, we have to find the maximum number of multiples of $A[i]$ in the array, where the indexes of the multiples should be less than $i$.
For example, given the array
36 40 ...
3
votes
2answers
75 views
How to sort a large list of elements where everything is sorted but k elements?
Assuming the list is very large, and $k$ is very small, what's the fastest algorithm to sort this list?
1
vote
2answers
48 views
Algorithm Design: Efficient O(n) algorithm to get the ith to jth largest elements in an array
I am trying to design an efficient algorithm that retrieves the ith to jth largest elements in an array. For example, if the following array is the input:
...
2
votes
0answers
45 views
Integer-array indexing (e.g. numpy.take) as function composition: where can I find more resources?
For context, one of Numpy's features is that an an array of integers can be passed as an index to an array, and this selects values at all of the specified positions, in any order with possible ...
0
votes
0answers
43 views
Is there an algorithm to compress a string array represented as pointers to a long string to pointers with a compressed version of the long string?
In a program I am writing, I represent an array of strings as a long string and have pointers point at the various substrings to present my array. E.g.
...
3
votes
1answer
70 views
Why is LinkedList useful?
If you implement a stack with a dynamic array-based with LinkedList you need more memory than with a dynamic array, and with dynamic array for insert in amortized cost is O(1), so the advantage of the ...
0
votes
0answers
26 views
Minimum amount of rectangles to create a 2-dimensional matrix
From this codegolf question.
Consider an $r$ by $c$ matrix of nonnegative integers, called $M$. You also have a zero matrix of the same dimensions, called $N$. A "move" consists of replacing a ...
1
vote
3answers
563 views
Why is heap insert O(logN) instead O(n) when you use an array?
I am studying about the arrays vs heap for make a priority queue
For check the heap implementation I am reviewing this code: Heap
, but I have the following question.
Heap is based on array, and ...
0
votes
0answers
54 views
Finding the rightmost element in an array of duplicate elements using binary search
i was reading Binary Search in the wikipedia and i came across this part of 'rightmost index of an element in an array of duplicate elements'. i understood the process of determining the leftmost ...
0
votes
1answer
53 views
Filler Algorithm
I am curious to know if there is an algorithm that, given an array of decimals and integers, and given an integer, returns a sequence in descending order, composed of those numbers of the input array ...
1
vote
1answer
54 views
Counting common values in two arrays
given two arrays of integers A and B of size m, with values in the
range [-n,n]. I want an algorithm to count how many common values are
in A and B , if a value is repeated we only count it once , ...
0
votes
1answer
95 views
Find pair with maximum Appeal value
Find pair with maximum Appeal value.
Input: Array
Output: index {i, j} ( i = j allowed) with maximum Appeal
Appeal = A[i] +A[j] + abs(i-j)
Example 1:
Input: [1, 3, -1]
Output: [1, 1]
Explanation: ...
