Questions tagged [arrays]

A sequential random-access data structure whose size can typically not be changed after creation.

Filter by
Sorted by
Tagged with
3
votes
2answers
540 views

Find the kth smallest element in an unsorted array of non-negative integers

I need to find the kth smallest element in an unsorted array of non-negative integer. kth smallest element is the minimum possible n such that there are at least kth elements <= n. The rub here ...
3
votes
1answer
8k views

How to prove that average complexity is N/2 for linear search in the unsorted array [duplicate]

All tutorials on algorithms show the complexity for the linear search in the unsorted array in the average case as N/2. I understand that the average case means the ...
3
votes
3answers
60 views

Why is subarray $A[p..k-1]$ empty when $k=p$?

I'm working through a proof of correctness for merge sort. I'm given a loop invariant for a for loop, which makes reference to a subarray $A[p..k-1]$. During the initialization step of the ...
3
votes
1answer
455 views

Maximum number of segments with no intersection [duplicate]

This is an interview question. Suppose you have an array of n segments, when each segment is a pair of two integers: start point and end point. For example: ...
3
votes
1answer
420 views

Sort an array based on dependencies

I have an array of objects, each of them has a numeric id and another array attached to them. The array in the object contains the dependencies of that object. Each dependency is an id from the other ...
3
votes
1answer
174 views

Find the smallest element greater than current element

my question is that given a list of integers (lets say A), for each element A[i], find the smallest element A[j] which could satisfy A[i] < A[j] and i < j. Return -1 if there is no such element. ...
3
votes
2answers
150 views

Proving an algorithm wrong

So I have this algorithm that outputs the largest value of an array: Input: $A[1,\dots,n]$, $n\geq 1$ Output: Largest value of an array ...
3
votes
1answer
717 views

Representing non-contiguous memory regions as a standard vector with O(1) access

What interesting alternatives are there for constructing an arbitrarily large static array from smaller scattered blocks of fixed-sized non-contiguous blocks of memory? This is similar to the ...
3
votes
2answers
92 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?
3
votes
1answer
75 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 ...
3
votes
1answer
34 views

Finding maximum takes at least $\lceil n/2 \rceil$ comparisons

We are given an array $A$ with $n$ elements, $n \in \mathbb{N}$ and all elements are in the set $\{1,2,3, \cdots, n \}$. I want to prove that finding the maximum in $A$ (that is, outputting the index ...
3
votes
1answer
68 views

Using bit arrays to solve crossword puzzles

I have read Crossword Puzzles and Constraint Satisfaction by Connor, Duchi and Lo and I am trying to implement this variation of crossword solving algorithm. I can't understand the bit array data ...
3
votes
1answer
54 views

Why are linked lists considered O(1) for in-middle insertion/deletion whereas dynamic arrays are considered O(n)?

I am struggling to understand why linked lists seem to be accepted to have better big-O performance than arrays for in-middle insertion/deletion. The performance differences between lists and arrays ...
3
votes
1answer
110 views

Returning m greatest elements from k sorted array

We have $k$ sorted arrays, $A_1[1...n_1],...,A_k[1..n_k]$, where $n_1+n_2+...+n_k=n$. How can we get the $m$ greatest elements in running time $O(k + m\lg k)$? I have tried to use MIN-HEAP size of $...
3
votes
2answers
749 views

match an array with a given set of arrays

We have a set of 24 distinct arrays, each array has 36 elements and each element can have one of 13 possible values. Then we're given an array X (this array is certainly part of our set) and we have ...
3
votes
1answer
68 views

Term for array of identical type and different types

What is proper terminology to distinguish between an array (ordered list) data structure in which each element is of identical type/class, and an array in which each element can be different?
3
votes
1answer
48 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 ...
3
votes
1answer
54 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 ...
3
votes
1answer
63 views

Efficient algorithm to replace list of integers with nearest bigger element

The original question was in the context of an array, but I just used a list without changing the length for easier debugging purposes of toString(). Given an ...
3
votes
1answer
706 views

Average-case complexity of linear search where half of the elements in the array are duplicates

I know that for an array of size n distinct elements, the Average Case complexity for linear search is as follows: A(n) = $\frac{n + 1}{2}$ However, I am having trouble coming up with the Average ...
3
votes
2answers
593 views

Modified counting sort algorithm?

So I have an array $A$, already sorted with CountingSort. Now I reduce one randomly chosen element $j$ with $A[j]>0$ by $x \in \{1 \dots A[j]\}$. I still have the counting array $C$, since I have ...
3
votes
2answers
113 views

What is this hash of array data structure called?

I've created a data structure that is a hash of arrays with a special property: the hash keeps track of the combined order in which items are appended to its arrays. For example (pseudocode): ...
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 ...
3
votes
1answer
54 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: ...
3
votes
0answers
139 views

How to find the top k pairwise product of in an array of integers?

Input: An array $a$ of integers $[a_{1}, \cdots, a_{n}]$, and a positive integer $k$. Output: The the top-k products of pairs in $a$. Example: $a = [7,6,5,4,3,2,1],k=3$ , output $(42,35,30)$, with ...
3
votes
0answers
469 views

Understanding the Polyhedral Model

I am wondering at a high level the mathematics of the Polyhedral Model. The polyhedral model (also called the polytope method) is a mathematical framework for programs that perform large numbers of ...
3
votes
0answers
27 views

What is the difference? [closed]

Is there any difference in between these two declaration: (1). char ch; (2). char ch[2] Actually the thing because of which this question arrived in my mind is the ending with '\0' i.e. null ...
3
votes
0answers
785 views

Sub-dividing a 2d array into regions

Suppose I have a array of real numbers with $n$ rows and $m$ columns. I want to consider possible ways of dividing that array into rectangular regions of three different possible types: a constant ...
2
votes
1answer
3k views

Time complexity of Dynamic Array via repeated doubling

When we implement dynamic array via repeated doubling (if the current array is full) we simply create a new array that is double the current array size and copy the previous elements and then add the ...
2
votes
3answers
588 views

Expressing semantics of an array as a function

An assignment questions asks the following: Consider an array 'var a : array[1..10] of real'. Express the semantics of this array as a function, defining the domain and codomain (you might ...
2
votes
3answers
257 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 ...
2
votes
2answers
347 views

Equality testing of arrays and integers in a procedural language

In terms of references and their implementation on the heap and the stack, how is equality testing for arrays different from that for integers? This is to do with Java programming, if you have a ...
2
votes
1answer
63 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
2answers
24k views

How is the formula for calculation in row/column major obtained?

In my book, this formula is given for calculation of address of row major order's element $[I,J]$: Address of $[I,J]$th element in row major order $= B + W[n(I-L_r)+ [J-L_c]]$ where B denotes base ...
2
votes
1answer
432 views

Linear time algorithm for array with distinct element

Given an array, if all the elements are distinct, can we find the count of elements which are lesser than an element and present to the left of that element in linear time if we have to do it for ...
2
votes
2answers
364 views

Finding the maximum of a bitonic sequence

Given to us is an array $B[1],\ldots,B[n]$ as input, which satisfies the following property: there exists a special index $i^* ∈ \{1, \dots , n\}$ such that $$B[1] < B[2] < \dots < B[i^*− 1] &...
2
votes
1answer
1k views

Median of two sorted arrays of different size in logarithmic time?

The solution given in Cormen is as follows: Reading this solution, the first doubt that comes in my mind is what if the median lies in array B. According to this solution, we are applying binary ...
2
votes
2answers
248 views

Number of pairs of indexes of two arrays such that one element is greater than the other

Let $A$ and $B$ be two arrays of size $n$. How many pairs of indices $i, j$ satisfy $1 \le i < j \le n$ and $A[i] > B[j]$? After quite a bit of thinking the best i had gotten to was make a for ...
2
votes
1answer
68 views

Should check all $2^n$ possibilities in array?

Suppose I have an array of numbers, and a function boolean isPrime(int n) that I'm allowed to use. Boolean isPrime(int n) ...
2
votes
1answer
235 views

What is total work of managing the dynamic array and why is it the same as for fixed array - O(n)

I'm reading the chapter on dynamic arrays in The Algorithm Design Manual book. Here is the excerpt from the book: Actually, we can efficiently enlarge arrays as we need them, through the miracle ...
2
votes
1answer
61 views

Costs of updating arrays to contain only zeroes

To initialize an array of length $n$ has complexity $O(n)$, as far as I understand. If I set every element to zero (with one code line), does that have time complexity $O(n)$ also? And in that case, ...
2
votes
2answers
762 views

Find the number of values between i & j(given as input) in an unsorted array in O(1) time

Given an unsorted array $A$ of $n$ numbers and inputs $i$ and $j$, can we find the number of values $i<k<j$ in $A$ in O(1) time complexity by doing some preprocessing? An additional requirement ...
2
votes
1answer
408 views

MinHeap represented by an array - two simple statements

I'm trying to prove/disprove two statements. I just want to make sure with you I'm on the right line. These are the following statements: Preface : Let A[n] be an array of min-heap (a min-heap ...
2
votes
1answer
47 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]$...
2
votes
1answer
34 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
2answers
84 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

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 ...
2
votes
1answer
489 views

Maximum Equal Sum K Subsequences

Given an array we need to find maximum equal sum $K$ subsequences, i.e. we want the sum to be maximized such that there are exactly $K$ non-overlapping subsequences each having the same sum. Example: ...
2
votes
1answer
148 views

Selecting a subtree in an array representation of a binary tree

Consider a zero-indexed array representation of a binary tree (as in a binary heap), where 0 is the root The left child of i is ...
2
votes
3answers
4k views

Given an array of integers and a value k, find the length of the longest subarray with max-gap no more than k

I'm struggling with this problem: you are given an array $A$ of $n$ integers and a number $k \in \mathbb{N} : k \neq 0$. The problem asks to find an algorithm that runs in $\Theta(n)$ that returns the ...

1 2
3
4 5
9