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
1answer
34 views

number of subsegments that contain A[i] as the minimum

I've recently been thinking about this problem. Given an array $A$ containing $n$ integers and an index $i$, find the number of subgements of $A$ containing $A[i]$ as their minimum. To better ...
2
votes
2answers
1k views

Proving at least $n-1$ comparisons are needed to test if an array is sorted

so I need to prove the following: Prove that $n-1$ comparisons are sometimes necessary to test whether an array with $n$ distinct elements is sorted in increasing order, for any $n \geq 1$. The ...
2
votes
1answer
147 views

Creating an O(n log n) time and O(n) space algorithm for counting pairs in an array

Given an integer array $a$, create a function, $\text{int} \; \text{pairs}( \text{int} \;a[\;])$ that returns the number of equal element pairs in the array. For example, given the array $a=[2,5,1,2,5,...
2
votes
1answer
80 views

Algorithm to create n arrays with maximum difference

Let's suppose I want to generate n equal sized boolean arrays with maximum "difference". - "Difference" in this case is defined as that the arrays share as low as possible fields with one another. (an ...
2
votes
2answers
657 views

Algorithm to check the distance between integers

I have the next problem, and I was wondering whether it exists a way to solve it without having to iterate around all the array in the worst case. I have a sorted array of pairwise distinct integers, ...
2
votes
1answer
42 views

Smallest subarray problem

Say you have an array of integers like [1, 2, 3, 4, 5, 6], the problem is to find the smallest way to break up the array into sub-arrays where each sub-array satisfies the following requirement: sub-...
2
votes
2answers
49 views

Finding largest farthest increasing pairs in array?

Is there a simple linear algorithm for finding in an array A two such elements that $A[i] > A[j]$ and $i - j$ is as large as possible? If one wants to actually return the indices, then linear ...
2
votes
1answer
38 views

Finding largest sum of $k$ elements below threshold

I was working on a project and am stuck in the middle unable to find an optimal method to solve this problem. Consider an array $A$ of $n$ elements. I have to choose $k$ elements such that the sum of ...
2
votes
1answer
60 views

Range of each building in array

I have two arrays, X and H, where X is sorted. X[i] represents the coordinate of building i. Y[i] represents the height of building i. If building i collapses, all buildings in the interval [ X[i]+1, ...
2
votes
1answer
218 views

How to search an almost sorted array faster than O(n) time?

Assume a 1-indexed array A[1...n], containing integers, where A[1] ≤ A[n]. The contents of the array have the following property : for 1 ≤ i < n, |A[i] − A[i + 1]| ≤ 1. Develop an efficient ...
2
votes
1answer
139 views

Summing two array using FFT: time complexity analysis

This is the problem : Given two arrays of $n$ elements A and B, let's define their sum as $$ A + B = \{ a + b \mid a \in A \text{ and } b \in B \}. $$ Calculate $A + A$ in optimal time given ...
2
votes
1answer
494 views

Find All possible Pairs in given Array

It is required to count number of unordered pairs in an array of size n , l[i]+l[j] = 2*l[k] , where 1<=i< j<=n and 1<=k<= n My Approach: ...
2
votes
1answer
2k views

What is the time complexity of memory allocation assumed to be?

It is well-known that dynamic arrays have an amortized $O(1)$ time complexity for adding one item, but a worst-case $O(n)$ complexity. This is because for particular values of $n$, there is no more ...
2
votes
1answer
3k views

How can I use prefix sum of an array to solve this problem?

I attempted this question on hackerrank. It seemed simple enough, and my program ran on small inputs. But my approach was "naive". And failed for more computationally intensive inputs. Here is the ...
2
votes
1answer
103 views

Algorithm to find the first person in front of $A$ that is shorter than $A$

We have an array of $n$ positive integers $a_0,a_1\dots a_{n-1}$ and let $a_n=0$. I need to build an array $b_0,b_1\dots b_{n-1}$ such that $b_i$ is the first integer larger than $i$ with $a_{b_i}\...
2
votes
1answer
3k views

Select a set of elements from a 2D matrix, such that each element comes from distinct row and column

We're facing following problem - an n * n 2D Matrix contains doubles (Java). Find a Set of elements such that Each element in the set comes from a unique row and column combination. That is, once ...
2
votes
1answer
131 views

Deamortizing a Las-Vegas randomized algorithm

Deamortization refers to the process of converting an algorithm with an amortized bound into one with a worst-case bound. For example, assuming you need to find the median of an array once every $n$ ...
2
votes
1answer
46 views

Algorithm for splitting an array into k sub-arrays

We want implement a data structure that have the following methods: Init(A,k)- Gets an array A with n different values and initialize our data structure that so it will divide A into k equally sized ...
2
votes
1answer
35 views

Minimum moves to “stabilize” an array

We have given an array of size $N$, consisting of positive integers, and an integer $H$. We also know that an array is stable iff $|A_i - A_{i-1}| \leq H$ for each $1<i<N-1$. We can modify the ...
2
votes
1answer
60 views

Thought process for the following problem?

We are given a 1-d array and we have to return the smallest array attainable after removing all the continuous same numbers. We can only eliminate those numbers which repeat continuously more than or ...
2
votes
2answers
43 views

Copying items in arrays while checking their indexes

Array $P$ of length $n$ is a permutations of $\{0, ..., n-1\}$ Write a code, which would in $O(n)$ create an array $R$ of length $n$, so for values $x_i, x_j \in P$, $R[x_i] < R[x_j]$ if $...
2
votes
1answer
640 views

Time complexity to find Median of Medians

I recently wrote my Grad school Admission test few days back and the following question appeared in the test. There are 'n' unsorted Arrays : A1, A2, ...., An. Assume that 'n' is odd. Each of A1, A2, ....
2
votes
1answer
47 views

Find four sets where each element from those four appears in at least two of those four sets

I have a list of sorted arrays ("sets") of integers $A_1..A_n$ where each element is unique w.r.t. the other elements in the same array: $A_i = \{x_{i,1}..x_{i,c_i}\}$ $x_{i,p} < x_{i,p+1}$ $A_i$ ...
2
votes
1answer
111 views

How to find efficiently the minimum modification to avoid close consecutive numbers?

I have an array of sorted numbers: arr = [-0.1, 0.0, 0.5, 0.8, 1.2] I want the difference (dist below) between consecutive ...
2
votes
1answer
45 views

Can this Arrow-Ring puzzle be encoded as an integer programming problem?

I would like to write a solver for these kind of Arrow-Ring puzzles. However, I can't encode all the constraints correctly. I noticed that Sudoku can be solved using integer programming and I am ...
2
votes
3answers
207 views

Closest divisors in array

Given an array $A[1],\ldots,A[n]$ of natural numbers, we have to construct a new array $B[1],\ldots,B[n]$, where $B[i]$ is equal to $A[j]$ for the minimal $j > i$ such that $A[j]$ divides $A[i]$, ...
2
votes
1answer
255 views

For given set of integers, find and count the pairs with maximum value of bitwise or

Let's say we have given set of integers $A = \{x_1, x_2, x_3, x_4, \dots, x_n\}$, consisting of exactly $n$ values, all of them positive integers. Now the problem is to find the maximum value of ...
2
votes
1answer
3k views

Correctness of algorithm to find maximum in array

I want to show correctness of "Algorithm to find maximum element in array" using induction and contradiction. ...
2
votes
1answer
2k views

How does the token method of amortized analysis work in this example?

Below is the description of the answer to a question which says the following: Design a data structure to support two operations for a dynamic multiset S of integers which allows duplicate values. ...
2
votes
1answer
4k views

Find Divisible Sum Pairs in an array in O(n) time

You are given an array of n integers a0, a1, .. an and a positive integer k. Find and print the number of pairs ...
2
votes
1answer
49 views

Wikipedia does not list insertion complexity for arrays - why?

Wikipedia does not list insertion complexity for arrays in the list of linked-list implementations. Is this because insertion operations are not defined on the array ADT?
2
votes
1answer
2k views

Finding median of three sorted array (the same length)

I think about following problem: There are given three sorted arrays $A,B,C$ (each of them is length $n$). Every array has distinct elements. Find median of union $A,B,C$. I consider following ...
2
votes
1answer
102 views

How can a set offer better search performance than an array

While reading the following tutorial on iOS development Working with Foundation (section on Sets near the bottom), I came across the following statement: "Because sets don’t maintain order, they offer ...
2
votes
1answer
702 views

Big Omega of 3-Sum Algorithm [duplicate]

An optimized algorithm for the 3-sum problem with an input array N has O(N^2logN) however I read that the Big Omega for this ...
2
votes
2answers
1k views

How can I have constant time initialization for multi-dimensional arrays?

For a regular array, I understand that if we have the tradeoff of space vs time, and we use more space to implement a Which, Data, and When pointers to the actual array, we can initialize the array in ...
2
votes
1answer
1k views

Finding farthest item in an array with duplicates

I have an array $A[]$ of size $L$, which contains numbers in the range $1 \ldots N$. Here $L>N$, so the array will contain repetitions. If $x,y$ are two numbers that are both present in the array,...
2
votes
0answers
38 views

Find a non-minimal sequence of elements covering the support set

Consider a sequence $s$ of $n$ integers (let's ignore the specifics of their representation and just suppose we can read, write and compare them in $O(1)$ time with arbitrary positions). Denote $\text{...
2
votes
3answers
338 views

Maximum number of multiples of an array element preceding it

Given an array of size $n$, we have to find the maximum number of multiples of $A[i]$ in the array, where the indexes of the multiples should be less than $i$. For example, given the array 36 40 ...
2
votes
0answers
57 views

Integer-array indexing (e.g. numpy.take) as function composition: where can I find more resources?

For context, one of Numpy's features is that an an array of integers can be passed as an index to an array, and this selects values at all of the specified positions, in any order with possible ...
2
votes
2answers
523 views

What is the meaning of uniform distribution of elements in an array?

I was going through the concept of Interpolation search and it stated that when the elements are "uniformly distributed", it takes O(loglogn) to search an element using interpolation search. Can ...
2
votes
1answer
69 views

How to reduce number of move operations in an array?

Say I have an array of numbers, e.g. [0, 1, 2, 3, 4, 5] and I want to end up with an array, e.g. [2, 1, 4, 0, 5, 3]. At my ...
2
votes
0answers
105 views

Minimum number of deleting palindromes to delete whole string

Let's say we have given array $A$ of size $n$. Our goal is to delete the whole array with minimum steps. In one step we can choose substring (consecutive elements from the string) and delete it only ...
2
votes
0answers
158 views

Min no.of operations required to convert an array to which it should contain elements of equal frequency

I have come across this tricky problem. An array of N elements should be converted to another array within k operations such ...
2
votes
0answers
63 views

Sort arrays $A$ and $B$ of the same elements using only comparisons between an element of $A$ and one of $B$

Premise: Let $A := [ k(1), k(2), ..., k(n) ]$ and $B:=[ l(1), l(2), ..., l(n) ]$ be two Arrays where $k$ and $l$ are permutations. (What I'm trying to express: $A$ and $B$ contain the same elements in ...
2
votes
2answers
60 views

Generate Evenly Distributed Pattern Based on Weights

I have an array of items $A = \{A_i\}, i \in I $ with integer weights $W_i, i \in I$. I need to build a function $f: I \rightarrow A $, that produces evenly distributed patterns of array elements ...
2
votes
1answer
43 views

Sorting Algorithm which prevents strings with at least one identical char from being next to each other

Imagine this Table: All combinations represented in the table (1,2 ; 1,3 ; 1,4 ; etc.) are stored as strings in an array with a total of (n^2-n)/2 elements (combinations). I'm looking for an ...
2
votes
0answers
42 views

Abstract Data Type

I have been studying data structures. In that I have come across topics like Array being defined as Power set of cross product of set of objects and set of natural number and list being defined as ...
2
votes
0answers
116 views

Counting subarrays where each number either doesn't occur or occurs odd number of times

We have given array $V$ of $N$ integers, we want to count the number of subarrays of the array such that each elements in the subarray either doesn't occur at all, or it occurs odd number of times. ...
2
votes
0answers
93 views

Counting inversions with index constraint

I have a series of line segments $l_i=(a_i,b_i)$ with $i=1,2,3...n$ $a_i$ and $b_i$ are their starting and ending points coordinates in $x$ axis. The question is how to find a algorithm that is ...
2
votes
0answers
247 views

Given An Array of Intervals, Find the Supersets

Suppose we have the following array of pairs representing start and end indices within an array. Think of them as an interval. I'll be using this term from now on. $[\left\{1,3\right\},\left\{4,9\...

1 2 3
4
5
9