Questions tagged [arrays]
A sequential random-access data structure whose size can typically not be changed after creation.
579 questions
0
votes
1
answer
30
views
Notation for element within an array range
I'm giving my students proofs of code correctness using loop invariants and induction, and I'm constantly running up against a notational problem. It's not the end of the world, but it is a ...
- 1,730
2
votes
0
answers
47
views
How does the equation to index non-leaf nodes of a binary tree 'array' in max-heap work for unbalanced binary trees?
According to Wikipedia's entry on binary heaps:
The Build-Max-Heap function that follows, converts an array A which stores a complete binary tree with n nodes to a max-heap by repeatedly using Max-...
- 123
0
votes
0
answers
117
views
Number of lexicographical swaps to make the array non decreasing
A lexicographical swap is defined as: At each step, pick the earliest possible inversion (i, j) (smallest i, then smallest j > i with a[i] > a[j]) and swap them.Repeat until the array is sorted.
...
- 11
1
vote
0
answers
44
views
How does passing an array slice to a function (which expects 1d array) work under the hood?
The motivation comes from modern Fortran, but I expect similar solutions in, say, Armadillo and Eigen libraries for C++. I hope the following example is clear even for someone who doesn't know Fortran....
- 11
-1
votes
1
answer
123
views
Ways to compact arrays
I'm looking for some common algos geared at storing arrays in a compact format using the underlying data particularities (and as such exceeding HEX and other ...
- 101
1
vote
0
answers
75
views
Transforming a sorted array into a maximally unsorted circular buffer
If I have a sorted array, e.g.
['A', 'A', 'A', 'B', 'B', 'B', 'B', 'B', 'C', 'C']
Is there an algorithm for turning this into:
...
- 111
0
votes
2
answers
254
views
Minimum sum of exactly K non-consecutive elements in an array
I ran into a problem while trying to solve this problem.
We're given an array costs of integers of length N, ...
user176008
0
votes
1
answer
105
views
Why are dynamic arrays called ArrayLists in Java?
The point of Java's ArrayLists is that they adjust their length automatically whenever items are inserted or deleted. If I understand it correctly, ArrayLists are wrappers around primitive arrays.
I ...
- 103
0
votes
1
answer
140
views
Smallest sum not obtainable using a subset of elements in array greater than the minimum element
I am solving a variation of the missing coin sum problem, modified to be as follows:
You have n coins with positive integer values. What is the smallest
sum greater than the minimum coin in the array ...
- 133
2
votes
1
answer
170
views
Sort the cols/rows of a 2D array of numbers using minimal swaps
Given a random array of 25 unique numbers in 5x5 2D array such as:
[
[2, 95, 86, 53, 38],
[32, 50, 37, 73, 98],
[49, 69, 35, 23, 97],
[96, 44, 65, 10, 17],
[39, 45, 67, 36, 99]
]
What is the best ...
- 51
1
vote
3
answers
189
views
Can there exist a deque like data structure that supports amortized $O(1)$ random access?
A lot of modern languages usually have a "list" or "vector" structure which allows for amortized $O(1)$ append and removal from back as well as amortized $O(1)$ random access.
I'm ...
- 375
1
vote
2
answers
2k
views
Arrays. Find row with most 1's, in O(n)
Suppose that each row of an $n \times n$ array $A$ consists of 1's and 0's such that, in any row of $A$, all the 1's comes before any 0's in that row. Assume $A$ is already in memory, describe a ...
2
votes
3
answers
132
views
Prove that the L1 distance between two arrays is minimized when both are sorted
Suppose you are given two arrays of the same length $n$, say $a$ and $b$ containing unique positive integers. The L1 distance between $a$ and $b$ is defined as:
$$d_1(a, b) = \sum_{i = 1}^n \lvert a_i ...
- 105
1
vote
1
answer
221
views
Algorithm to sort array into K increasing subsets?
Let's say we got an array of size n with real numbers, and a natural number k. n must be multiple of k. We want to sort the array in a way that, when we divide this array into k subsets of equal size, ...
- 11
1
vote
1
answer
199
views
Finding the smallest root
We are given an array $a$ of $n$ integers, such that the difference between each element $a[i]$ and the adjacent elements $a[i-1]$ and $a[i+1]$ is at most $1$.
Define a root of $a$ as an index $k$ in $...
- 6,087