Questions tagged [arrays]

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

Filter by
Sorted by
Tagged with
2
votes
0answers
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 ...
2
votes
0answers
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 ...
2
votes
1answer
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 ...
1
vote
2answers
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) ...
1
vote
2answers
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 < ...
1
vote
3answers
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 ...
1
vote
3answers
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 ...
1
vote
3answers
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: ...
1
vote
2answers
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 ...
1
vote
2answers
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 ...
1
vote
2answers
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: ...
1
vote
2answers
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 ...
1
vote
3answers
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?
1
vote
2answers
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 ...
1
vote
2answers
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....
1
vote
1answer
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 ...
1
vote
1answer
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 , ...
1
vote
1answer
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 ...
1
vote
2answers
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 ...
1
vote
2answers
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: ...
1
vote
1answer
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$. ...
1
vote
1answer
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. ...
1
vote
1answer
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$)...
1
vote
1answer
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 ...
1
vote
2answers
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 ...
1
vote
3answers
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 [...
1
vote
1answer
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, ...
1
vote
1answer
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}$ ...
1
vote
2answers
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 ...
1
vote
1answer
119 views

Finding the element that occurs more often than the other

I want an algorithm that calculates which element, among two, appears more often than the other in a sorted array. The array will have only two types of elements. Example : $aaaaaabbb$ Here $a>...
1
vote
1answer
36 views

How to find the size of gaps between entries in an array so that the first and last element of the array is filled and the gaps are all of equal size?

I have an array a of n entries. I need to place a token on the first and last position of that array, so a[0] = 1 and a[n-1] = 1....
1
vote
2answers
43 views

Amortized time for dynamic array

I'm struggling to understand one part from the book "Cracking the coding interview". The author states inserting an element in a dynamic array is $O(1)$ most of the time, except when the array is full ...
1
vote
2answers
34 views

Given a list of integers and a target integer, return the number of triplets whose product is the target integer and two adjacent triplets

Question: Given a list of integers (possibly negative) and a target integer, return the number of triplets whose product is the target integer and two of the triplets must be adjacent. More ...
1
vote
1answer
27 views

Longest subarray with at most two different values - Runtime complexity for a DP solution

Consider the problem of finding, for a given input array, the longest subarray with at most two different values. For example: ...
1
vote
1answer
50 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
1answer
98 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,...
1
vote
2answers
83 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 ...
1
vote
1answer
63 views

How to remove objects from an array most efficiently?

I am wondering if I can rearrange an array faster when I would like to delete more than one object. You are given a List: 1 2 2 3 4 5 7 And now you want to delete every "2" in the list. So what I ...
1
vote
2answers
63 views

Sequential subsequence removal with arbitrary predicate

I want to extract sub-sequences from a sequence of float values. The "scale" and range of these values is arbitrary (as I can manipulate it at will) but the "shape" is consistent. For a visual ...
1
vote
1answer
36 views

What is an array that can be iterated circularly an infinite amount of times called?

I have a feeling that the answer is either a "circular linked list" or a finite state machine, but the answer is probably a circular linked list.
1
vote
2answers
252 views

2D peak reasoning to move to a half

You have a 2D integer matrix given. An element is a peak element if it is greater than or equal to its four neighbors, left, right, top and bottom. For example neighbors for A[i][j] are A[i-1][j], A[i+...
1
vote
1answer
54 views

Algorithmic Design to Undo Rotation of Array

An array $A$ of $n$ distinct, ascending integers is rotated to the right by $k$ positions, resulting in the array $A_{k}$. That is, the element at index $i$ in $A$ is moved to index $(i+k)\mod n$ in $...
1
vote
2answers
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 ...
1
vote
1answer
67 views

How to check if $m$ numbers in a sequence satisfy a condition, such that all these numbers are spaced apart by at least $k$?

Suppose we have a sequence $s$ with $n$ elements from $s[1..n]$. I want to check if there exists $m \leq n$ elements in this sequence that each satisfy some simple condition (that can be tested in $O(...
1
vote
1answer
58 views

Number of elements with lower index equal to some element, for all items on an array

Let $A$ be an array of size $n$, and $f(i, r, a_r)$ be the number of indices $k$ such that $a_k$ = $a_r$ and $i \le k \le r$. Example to clarify: Imagine the array: $[1, 2, 3, 2, 2, 3, 4, 5]$. $f(0,...
1
vote
2answers
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[1] < A[2] < \dots < A[k]$ write pseudocode for an algorithm that ...
1
vote
2answers
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) ...
1
vote
1answer
313 views

Sum of two elements in set evenly divisible by k

I have gone through this particular problem in hackerrank. You are given an array of $n$ integers, $a_0, a_1, a_2 , \ldots, a_n$, and a positive integer $k$. Find and print the number of pairs $(i,...
1
vote
1answer
139 views

Partition array - elements non-negative and negative. Minimal number of replacements of elements

I consider following problem: It is given array with numbers, for example $[-2,0,1,-324,213,321,-2]$. The problem is: replace elements such that negative numbers precede the non-negative. For our ...
1
vote
2answers
178 views

Perform an operation on an array in O(n)

I'm required to perform the following operation on an array in O(n): P[1..n] is an array of positive integers. For each index 'i' in the array, I must find how many "cells" I can advance toward the ...

1
3 4
5
6 7
9