Questions tagged [arrays]
A sequential random-access data structure whose size can typically not be changed after creation.
564
questions
0
votes
0
answers
31
views
How do i make a 2d array as same as i possibly can with another one?
Say i have an 2d array A of nxn size, int values already given for each item.these values can be the same or different.
There's gonna be another nxn array B being input. I can only interchange one row ...
0
votes
0
answers
12
views
How do you understand Systolic Arrays?
I'm working on a problem from the Digital Design and Computer Architecture course on Systolic arrays.
The question set up is as follows:
The following diagram is a systolic array that performs the ...
- 101
1
vote
1
answer
63
views
Sorting rational numbers in linear time
I am currently studying algorithms and computational complexity at University.
I have recently got through three questions I found in an old exam:
Is it possible to sort in asymptotically linear time ...
- 11
0
votes
1
answer
49
views
Prove with potential method that dynamic table with $q > 1$ expansion runs in amortized constant time
Suppose I have a dynamic table supporting $Insert$ procedure, which sets an input value after the tail of the dynamic table. If the underlying table is already full, we multiply its size by $q > 1$....
- 52
0
votes
0
answers
24
views
Finding minimum in a descending rotated sorted array with duplicates
For this question (154. Find Minimum in Rotated Sorted Array II
), I have a solution:
...
- 103
1
vote
2
answers
64
views
Why is `3[arr]` notation of accessing elements in array is not used?
Today, I came across the notation 3[arr] in C++, and I was surprised to find out that it's a valid way to access array elements. For example:
...
- 128
0
votes
0
answers
14
views
Periodicity of substitution system
I’m interested in substitution systems: maps which use a set of rules to transform elements of a sequence into a new sequence.
For simplicity we will consider here only binary 1-D arrays.
Unlike the ...
- 111
0
votes
0
answers
11
views
Keeping in a list a list of recent insertions/removal to/from a list of lists
I have a list of lists T.
I stress test my database software by randomly adding and removing sublists and elements of sublists to/from T and from/to my database. (After this I compare T with the ...
- 433
2
votes
1
answer
102
views
Data structure for querying maximum of a rolling total
Let $A = \{a_1, \ldots, a_n\}$ be a set of numbers and $w$ be some number. Define $p_w^{A}: \mathbb{R} \rightarrow \mathbb{N}$ as $$p_w^{A}(r) = |\{i \in \{1, \ldots, n\} | r \leq a_i \leq r + w\}|.$$ ...
1
vote
1
answer
63
views
Check if Two Arrays Sorted in Decreasing and Increasing Order Satisfy a Condition
Given 2 arrays $A, B$ each of size $n$. If we want to find if the two arrays satisfy the condition that $A[i] + B[i] \ge k$ for all indices $i$, it's sufficient to fulfill 3 conditions below:
Sum of ...
- 493
0
votes
0
answers
38
views
Researching the complexity of a dynamic array with insert-last(x) and delete-last() operations
In this question I need your help researching time complexity of a dynamic array with insert-last(x) and delete-last() operations:
We define a data structure and call it dynamic array, we define the ...
- 1
1
vote
1
answer
347
views
Finding equal-sum subsets from two arrays
Consider the following problem: You are given two integer arrays $A$ and $B$ of size $N$ and $M$, respectively. You are guaranteed that $1 <= A[i] <= M$ and $1 <= B[i] <= N$ for all $i$ (...
0
votes
0
answers
14
views
Finding a ArrayList Connection (representing Subway Lines) with Recursion
I have this ArrayList (called linArray) (and this only) that contains Subway exchange stations (first the station name and then the lines you can exchange to at that station):
...
0
votes
3
answers
114
views
How is a direct address table different from an array?
I found this from this PDF (https://web.stanford.edu/class/archive/cs/cs161/cs161.1168/lecture9.pdf)
- 161
0
votes
1
answer
67
views
Can contiguous arrays be lazily evaluated?
Contiguous arrays with variable length, such as C++'s std::vector, have been a major sequential container for languages whose evaluation is eager. However, it has ...
- 335
0
votes
2
answers
75
views
Speeding up an array search for duplicate
I was tasked with writing a function that finds the value of an element that is the first duplicate in an array to be encountered. For the array
[2, 1, 3, 5, 3, 2]
...
- 101
0
votes
1
answer
97
views
Can somebody explain to me the concept of mutability with respect to a NumPy array?
From the NumPy documentation:
"NumPy arrays have a fixed size at creation, unlike Python lists (which can grow dynamically). Changing the size of an ndarray will create a new array and delete ...
- 101
0
votes
1
answer
74
views
Algorithm to find minimum amount of swaps to convert array A into array B with repeated elements
I'm trying to create an algorithm that finds the minimum number of swaps to convert array A into array B. In this case the arrays can only contain the numbers 0, 1 or 2.
So for example: given ...
- 25
1
vote
2
answers
128
views
How do I find the most even combination for two arrays
I have two arrays that both contain $n$ elements (positive, non zero, not negative)
$\{x_1\dots x_n\}$
$\{y_1\dots y_n\}$
I want to pair them up optimally, one from each array, so that the pairs come ...
- 11
1
vote
0
answers
71
views
Finding the total work of an array list expansion effort
Suppose we are given an array-based list data structure. Suppose that its initial capacity is
$m > 0.$ When appending an element to the end of the list, if the list is full, we extend its capacity ...
- 52
-1
votes
2
answers
277
views
Local minimum in array, find $O(\log n)$ algorithm
Main Problem
Given an array $A[1...n]$ ($n \geq 3$) of distinct integers with at least a local minimum, output a local minimum.
A local minimum is an integer $1 < i < n$ such that $A[i-1] > A[...
- 1
0
votes
0
answers
53
views
Is this minimizing problem NP-hard?
We have $c$ arrays of positive integers, named $j[1],j[2],j[3]..,j[c]$. We know that the length of $j[i]$ is $c-i+1$. In addition, the sum of the numbers of $j[i]$ is greater than or equal to the sum ...
4
votes
1
answer
174
views
Possibly Tractable Variation of Suguru Puzzles
I'm currently investigating the computational complexity of a modified one-dimensional Suguru puzzle. The general Suguru puzzles were recently proven to be NP-complete (see here). My investigation ...
- 43
1
vote
2
answers
84
views
Division by zero in APL: assign return value 0 or 1
Recently I began learning a couple array based programming languages: Dyalog APL and BQN. And I cam across this peculiar manner in which division by zero is handled in Dyalog APL. Using the in-built ...
- 113
0
votes
0
answers
23
views
Succinct array datastracture
Is it true that there is no known succinct data structure that has integer array (vector) functionality? Desirable operations would be:
append O(1)
access(i) - returns i-th item O(1)
iterate(i..j) - ...
- 141
-2
votes
2
answers
264
views
Modified Bubble Sort's time complexity
I have an array (of hundreds of numbers) and I need to sort them. In this case, I used Bubble Sort because of the better time complexity compared to other algorithms, $\Theta(n^2)$.
...
- 3
-2
votes
1
answer
65
views
Is there an algorithm that can get the minimal element of a min-heap in O(log* n)?
I came across this question when studying for an exam:
given a min-heap that has no prime numbers in it, is there an algorithm that can get and delete the minimum of that heap in O(log* n) ?
The ...
- 1
0
votes
2
answers
143
views
Can you help me in finding an algorithm that finds the first unique number in an array with lowest position?
I have the following problem to solve:
Given a non-empty array A consisting of N integers, the task is to find the first unique number in the array. A unique number is defined as a number that occurs ...
-1
votes
2
answers
388
views
Longest increasing subsequence when a number can be added to all numbers in a subarray
A sequence $(a_1,a_2, \dots, a_n) $ and natural numbers $n$ and $k$ are given.
We want to calculate the longest (strictly) increasing subsequence of sequence $(b_1,b_2, \dots, b_n)$ for which there ...
- 47
2
votes
2
answers
140
views
Producing "moves" to permute one array to another
I have 2 arrays, A and B, which each contain the same N elements, but in a different order. (A different permutation)
There are also no duplicates in A and B.
I'm trying to devise an algorithm which ...
- 23
1
vote
2
answers
95
views
Convert lower-left matrix triangle 1D index to row, column
How can I convert a 1D index in the lower-left triangle of a grid into a row and column?
For example, consider this table of 1D indices, indexed by row and column
...
- 187
0
votes
1
answer
349
views
Finding majority element in $\mathcal{O}(nlogn)$ time
I am trying to build the logic behind a divide and conquer algorithm that will find the majority element in a matrix $A$ with $n$ elements in $\mathcal{O}(nlogn)$ time.
I thought that in order to make ...
- 225
1
vote
1
answer
675
views
Minimal number of positive intervals to cover all positive elements
I'm struggling in finding a correct way to approach this, I'm aware that this problem is solvable using dynamic programming, and this problem somehow relates to the "max non-contiguous subarray&...
- 315
0
votes
3
answers
136
views
is there an O(n^2) approach to this problem?
Given an array of N elements, I need to split it into k subarrays, where k can be between 2 <= k <= N. A sub-array's score is determined by:
(left boundary point - right boundary point of the ...
0
votes
1
answer
121
views
Finding number of combinations of numbers from multiple arrays that add up to a given value
Let $ A $ be an array of $ n $ integer arrays with unknown lengths and $ s \in \mathbb{Z} $ a given number. I want to find the number of combinations of numbers from each array, such that their sum ...
- 101
0
votes
1
answer
42
views
Construct an objective function that favors the sorted permutation
I was looking into complexity theory and disappointed by the fact that a problem as simple as sorting an array isn't in the class $P$. This is because the class is defined only for decision problems (...
- 305
6
votes
2
answers
2k
views
Why does the order of the nested loops matter when solving the Coin Change problem?
The Coin Change problem is stated as:
Given an integer array coins[ ] of size N representing different
denominations of currency and an integer sum, find the number of ways
you can make sum by using ...
- 171
0
votes
1
answer
49
views
Is this an inversion problem?
I understand that total inversion in a sequence is the number of swaps that need to be done, to sort the sequence. And the best approach to solve this problem is to count swaps in a merge sort of the ...
2
votes
4
answers
114
views
Algorithm that finds 4 "O"s or 4 "X"s on a diagonal, horizontal, or vertical
My algorithm homework revolves around matching 4 "O"'s or 4 "X"'s on a diagonal, horizontal, or vertical. ...
- 123
-2
votes
1
answer
36
views
Inversion array of a given array
Let A[1...n] be an array of n distinct numbers. The ordering of the numbers is any permutation of [1,2,...,n]. An array Inv_A is defined as follows: Inv_A[i] = number of elements A[j] such that j<i ...
1
vote
1
answer
50
views
Are there adaptive algorithms/data structures for sparse and non sparse vectors?
A sparse 1D array of integers is commonly encoded as pairs of [index, value], which consumes 2 memory spots per value.
A dense 1D array is commonly encoded as a linear array of values [value1, value2, ...
- 131
1
vote
1
answer
72
views
Unable to understand how the while loop extracts the least number of coins with given sum
I was reading this classical Coin Problem (7.1): Given a set
of coin values coins = {c1, c2,..., ck} and a target sum of money n, our task is to
form the sum n using as few coins as possible.
I fully ...
- 13
0
votes
0
answers
39
views
Display XY data on computer
I would like to experiment with displaying the output of an analog to digital converter on computer. Samples of the ADC output would determine the intensity of one pixel.
The input to the ADC is an ...
25
votes
3
answers
3k
views
Array access is O(1) implies a fixed index size, which implies O(1) array traversal?
Arrays are generally presented as data structures with $\Theta(N)$ traversal and $\Theta(1)$ random element access. However, this seems inconsistent:
if array access is really $\Theta(1)$, this means ...
- 380
-1
votes
2
answers
356
views
Minimum absolute sum of 2 elements from 2 different lists
I am currently stuck on this problem, it is from a very highly competitive contest and so it is highly difficult as well. Below is the statement:
...
0
votes
2
answers
77
views
Finding an element within an array that satisfies some rule
I saw a question on an old exam in my university course of DSA and I am not sure if the question is far too easy or if I am missing something.
The question is :
Given an array A that consists of N ...
- 229
1
vote
0
answers
172
views
Minimum swaps to rearrange array so that the same numbers are in consecutive positions
Problem: Given an array of $N$ integers in range $[1,M]$, count the minimum number of swaps to rearrange array such that the same values are in a row.
For example, given an array $[1,2,1,1,2,1,2]$.
...
- 159
0
votes
2
answers
363
views
Why do the pointers in Two-pointer algorithm move only towards each other?
Problem statement- Given a sorted array, print out the pair of elements of the array that have a sum of K, where K is a whole number.
The solution to the above problem goes like this:
With using the ...
- 1
2
votes
2
answers
841
views
How can I apply binary search to find two adjacent increasing elements in an unsorted array?
I need to write a function that gets an array of numbers $a$ as an input and returns an index $i$ such that $a[i]<a[i+1]$ if it exists, if such $i$ doesn't exist return $-1$. (return any index $i$ ...
- 164
0
votes
2
answers
3k
views
Maximum subarray sum of given length range
Can anyone please help me solve this better than $O(|a-b| \cdot n)$?
Given an array of both negative and positive numbers, we want to find the maximum sum of the elements in contiguous subarray having ...
- 53