# Questions tagged [arrays]

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

428 questions
Filter by
Sorted by
Tagged with
96 views

### Array counter with mimimum find

I need to implement data strucure such as array, but with the following interface: GetMin() - Returns the minimum from the array IncRight(index) - Increases all values from specified index to the end ...
105 views

### Why can't fractional cascading be used on two unrelated arrays?

According to both Wikipedia and my professor (see question 5.1), fractional cascading has to be done on arrays with related data. The specific question: A fellow student wants to compactly store ...
80 views

### Find the nearest sum to a given number of two elements in sorted matrix

Given a sorted $n\times n$ matrix $A$ of real values. That is $a_{ki}<a_{kj}$ and $a_{it}<a_{jt}$, when $i<j$. Propose and algorithm, finding two elements of this matrix with the sum nearest ...
285 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) ...
72 views

### What does the “0 ≤ K < N-1” expression means?

Given the following statement: "A nonempty array A consisting of N integers is given. Any integer K, such that 0 ≤ K < N-1, splits array A into two non-empty parts" What does the 0 ≤ K < ...
63 views

### Algorithm to compute maximum of blocks

We have $n$ numbers lying on a circle, where $n$ is even. We want to compute the maximum of any $n/2$ consecutive numbers (so, we should get $n$ values in total). One algorithm is to compute the ...
853 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 ...
1k views

### Algorithm to find k elements following the median in sorted order

I have the following problem: Given an unsorted array A of size n, print the first k elements in A larger than its median. Here's my approach to the problem: ...
208 views

### How can I get O(1) prepend on a random-access list?

I need a data structure that has the following operation: $\operatorname{prepend}([x_{n - 1}, ..., x_0], x_n) = [x_n, ..., x_0]$ $\operatorname{prepend}$ should be in $O(1)$. Assume that you have ...
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 ...
57 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: ...
1k views

### Can we apply binary search for finding key 'x' in unsorted array?

Suppose we are given A, an array of size n, comprised of an increasing sequence of numbers followed immediately by a decreasing one. What is worst case time complexity of optimal algorithm to ...
6k views

### What are the uses of multi-dimensional arrays? [closed]

While studying arrays a question came to my mind. If only 1D and 2D arrays can be used, then why multi-dimensional arrays exist? Is there any use of multi-dimensional arrays?
267 views

### Any algorithm better that O(N*logN) for a problem of finding student with largest average score in a list of N scores of the form StudentID, score

Question: Suppose you are a given a csv with N lines of the form StudentID, score. Multiple lines can have same student-ID. Find the student with maximum average score I can't think of any way to ...
489 views

### How to denote an array in writing paper

How can I represent an array when I am writing to show an algorithm in writing paper. Like Pi is represented by Greek letter. We use that Greek symbol to denote the value of Pi, Kind of like a pointer....
872 views

### Sorting algorithm that moves element to a 2-dimensional array

I had an idea for a sorting algorithm wich is very fast, but can (potentially) use a lot of memory. I'm not a Computer Science student/graduate, only a self-taught programmer so I don't know how to ...
66 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 , ...
54 views

### If an array is full of the same integer, like 0s or 1s, are they all the peak of the array?

I am learning the MIT course Introduction to Algorithms. The professor is saying In particular, as an example, position 2 is a peak if, and only if, b greater than or equal to a, and b greater ...
97 views

### Get indexes of unique elements in two different arrays in linear time

I have two array of the same set of elements, say for exemple: $a_1 = [x_1, x_2, …, x_n]$ and $a_2 = [y_1, y_2, …, y_n]$ so that $i \neq j \Rightarrow x_i \neq x_j$ Is it possible, in linear time, to ...
107 views

### How to predict the length and offset of the sequence in and array?

I have an input string similar to ABCDEFGHIJK from which a series of sequences has been generated into an array as following: ...
477 views

### Counting subarrays that satisfy either of two conditions

We have an array of integers $a[]$, with each $|a[i]| \leq 10^{6}$, $size(a)\leq10^{5}$, and $a[i]-a[i-1]\leq100$. Then we define the term range as a subarray $[x,y]$ of the array $a[]$, $x \lt y$. ...
1k views

### Efficient algorithm for a modified stack to pop the smallest element

I was practicing the following problem : There are a total of $N$ operations. At each operation, you can either add an element to the top or remove several elements as described below. ...
224 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$)...
2k views

### Find all local minima in a big 2d array

Assume we have a big 2d array. All its elements are either zeros or natural numbers. A local minimum is an element that is less than all its 8 neighbors. Is there an effective algorithm to find all ...
110 views

### Sort already sorted array - after changing several elements

Problem: Given $S$ — a sorted array where some of the elements were randomly changed, assuming that you're provided with an $S_1$ — an array of indexes of changed elements. Design an ...
98 views

### Beginner help with Arrays & Complexity

My goal is to create a method that gets an array that only has 1's and 0's in it, and then turns every number into the amount of 'steps' it is away from the closest 0, left or right. So for example [...
91 views

### Selecting a random 'bad' element from an array of $n$ values in $O(n)$ time and $O(1)$ space without knowing how many bad elements or where they are

I have an array of elements $A = [x_0, x_1, \ldots, x_n]$, such that for some $0 \leq k \leq \frac{n}{2}$, there are $k$ 'bad' elements in $A$, but I don't know what indices they are at, or indeed, ...
214 views

### Sorting array containing elements from $\{1,\ldots,k\}$ in place in $O(n\log k)$

An array $a[1,\ldots,n] \subseteq \{1,\ldots, k\}$ is given, where $k < \sqrt{n}$. Our goal is a project algorithm which sorts it in place and in time $O(n\log k)$. We assume that $k < \sqrt{n}$ ...
79 views

### Sorting a sorted array after increasing several elements

I know that most of the efficient sort algorithms can run with a complexity of $O(n\cdot log(n))$, but this is given an unsorted array. However, given that the initial array is already sorted, is ...
119 views

723 views

### 1D Peak-finding problem, how to derive the formula?

I couldn't find a good answer to how this formula was derived for the divide and conquer algorithm in a 1D Peak-Finding problem. About the problem Basically, there's an array of numbers and we want ...
67 views

66 views

### Finding an index such that $A[i] = i$ in a strictly increasing integer array

I'm looking for a hint for solving the following problem : Given an array $A[1, \dots, k]$ of integers where $A < A < \dots < A[k]$ write pseudocode for an algorithm that ...
830 views

### How do you find all integers in a sorted array of size n that appear n/k times, given that 0 < k < n, and in O(k log n) time?

This looks like a typical divide and conquer algorithm, but with a few tricky parts. It looks like we want to do k operations and divide the array in half at each step because of the O(k log n) ...