Questions tagged [arrays]

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

80 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
7
votes
0answers
470 views

What is the average-case running time of Fun-sort?

I read this paper: http://www.sciencedirect.com/science/article/pii/S0166218X04001131?np=y (you can check the PDF online for free), and I translated section 4's Fun-sort algorithm (correct me if I'm ...
6
votes
1answer
163 views

Sort 2D arrays so that cost of reaching new position as described at each iteration is minimized

Problem is as following: We are 8 trumpet players in an orchestra. There are for example 4 parts so there are always two players on the same part. Now, there are not always the same two players ...
5
votes
1answer
7k views

Merge two sorted arrays without using additional memory

We have two sorted arrays of integers. Without using additional memory we need to merge these two arrays such that the smallest numbers are in the 1st array and the remaining numbers are in the ...
4
votes
1answer
101 views

Sort array of duplicate integers in place

Given an array of integers within [1, n] where n = size of array, some elements may appear more than once. Could we sort it with just 1 extra space and in O(n) time?
4
votes
0answers
1k views

Find the median of two sorted arrays of different size in O(min(log(n),log(m)) complexity

Given two sorted arrays of length m,n, how do I find the median of the union of these two arrays in O(min(log(n),log(m)) time? I've been trying to come up with an algorithm (and a proof) for several ...
4
votes
0answers
687 views

Algorithm for solving rectangle puzzle

Early note: This is not homework. I simply regularly create ideas in an attempt to teach myself a language. For what it's worth I'll be using Javascript for this. That said, I haven't been able to ...
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
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
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
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
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\...
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
0answers
28 views

Matrix multiplication over range in $O(n)$

Let $Q$ denote the number of queries. I have a $25 \times 25$ matrix in each cell of an array of size $n$. Let us denote this array by $A$. It's a special matrix, more specifically, all elements are $...
1
vote
1answer
58 views

Generate all combinations of a set/array with specific conditions

Apologies if this isn't posted in the right stack exchange, but I'm trying to come up with an algorithm that generates a set of sets ('set' as synonymous with 'array') with the following conditions: ...
1
vote
0answers
13 views

Minimising total access time to elements in an array which is accessed sequentially

Starting with two examples: for(i = 1; i<10; i++) {B[i] = 0;} for(i = 1; i<10; i++) {B[2i] = 0;} In the first example, ...
1
vote
0answers
75 views

finding the parent index in an interval heap (stored on an array) given a child index

an interval heap is a binary tree stored on an array where the size of each node is 2. i would like to be able to find the index of a parent and find one of the child indices given the index of a ...
1
vote
1answer
86 views

Find number of triples that sum up to zero in query-intervals

My problem is that we have an array of $N$ integers $(N <=5000)$ on the interval $[-10^6,10^6]$. We also have $Q$ queries $(Q <= 10^5)$ giving us some range in the array. For each query, we ...
1
vote
0answers
16 views

When was the dynamic array first introduced as an example for amortized analysis?

I'm writing a report on amortized analysis, and I'm using the example of a dynamic array to explain each method. I think it would be nice to add a reference to when this example was first used, as it ...
1
vote
0answers
26 views

Intersection of 2 arrays

Here is a question i came across : Given two arrays, write a function to compute their intersection.Here we will allow the duplicates. Note: Each element in the result should appear as many ...
1
vote
0answers
68 views

Is it possible to write a fully-decidable type system for the J language?

I'm experimenting with the J array language, a dynamically-typed array language with mutable assignment, subtyping, and function overloading (just like traditional APL). It is unclear to me whether ...
1
vote
1answer
96 views

Job scheduling approximation

In the course notes for Stanford MS&E-319: https://web.stanford.edu/class/msande319/lec1.pdf Lemma 5 is given as: The approximation factor of the modified greedy [scheduling] algorithm is 4/3....
1
vote
0answers
40 views

Recurrence Relation for Column Major Form of multidimensional array

A two dimensional array is stored in column major form in memory if the elements are stored in the following sequence $$A[0][0] A[1][0] A[2][0]...A[n_1-1][0] ... A[0][1] A[1][1] ... A[n_1-1][1] .... A[...
1
vote
1answer
379 views

Array subset division with equal sums

Today I stumbled upon a problem which looked like the partition problem but certainly is different. Given array of positive integers, guaranteed to not be divisible into two continious subsets of ...
1
vote
0answers
180 views

How does prefix summing the count histogram in counting sort result in an array of output indices?

My implementation of counting sort is based on the description I found here. I've also included my code in this REPL, but here it is: ...
1
vote
2answers
207 views

FInding the combination with the least number of elements from and array of integers, given an integer sum

I'm doing and assignment where the problem is to find the combination with the least number of elements form an array of integers, given an integer sum. I have solved this using a gready algorithm ...
1
vote
0answers
23 views

How to chose the condition for expand in hash-table?

How can I chose the condition for expanding of the array in chain-hashing if I want that given some cell (that contains elements) , the number of cells that I need to move about them is O(1) until the ...
1
vote
0answers
336 views

Online algorithm to find shortest subarray containing all k-elements

We have given array of $n$ integers in the range $[1, k]$. We want to design algorithm that can modify the array and also find the length of the shortest subarray containing at least one of each ...
1
vote
0answers
1k views

To find median of k sorted arrays of n elements each in less than O(n*k*log(k))

How to find median of k sorted arrays each of length n? Note that total elements would be n*k. I know it can be done in O(n*k*log(k)) using merge technique. I am looking for a better time efficient ...
1
vote
0answers
520 views

Algorithm to split an array into minimal number of subarrays where sum of their elements is less than or equal a given one

Title of the question pretty much summarises the question. Here is a concrete example of what I'm trying to achieve with no success. Let's say we have a sorted list (but sorted is not a requirement) <...
1
vote
0answers
165 views

Maximize the minimum element

We have an array of $N$ positive elements. We can perform $M$ operations on this array. In each operation we have to select a subarray(contiguous) of length $W$ and increase each element by 1. Each ...
1
vote
0answers
145 views

Representing multisets by a bit vector

What would be the most space-efficient way to represent a multiset (a set that can contain duplicates) using a (static) bit string (bit vector, bit array, etc.)? All of the elements in the multiset ...
1
vote
0answers
72 views

Create an array minimizing sum of square deviations to another array

Problem Let y be an array of float numbers (of length $n$) bounded in the range [0,1]. I am trying to compute the array x that ...
1
vote
0answers
996 views

Can partial sums of a counter array be computed in O(log n) time?

Let $A[1 . . . n]$ be a given array of $n$ integers, where $n = 2^m$. The following two operations are the only ones to be applied to A: Add(i, y): Increment the value of $A[i]$ by $y$. PartialSum(k)...
1
vote
0answers
350 views

Finding max average value subrectangle at least a certain size in a 2-d sparse array

So Kadane's dynamic programming solution for finding the maximum sum contiguous subinterval in a 1-d array runs in linear time, and can be adapted to give a best-known $O(m^2n)$ time solution to find ...
1
vote
0answers
794 views

Longest Increasing Subsequence

I got no responses on stackoverflow, so I'm asking here: How useful is the LIS (Longest Increasing Subsequence) problem in tackling other CS problems? There are a few algorithms, using patience ...
1
vote
1answer
118 views

Algorithm to find out the number of times a number occurs consecutively in an array in a range specified

I have an array say 8 3 5 4 4 4 4 4 3 2 7 11 12 7 7 7 7 1 2 total =17 elements now you are given a range say [2,11] both included ,now you have o find out the ...
0
votes
0answers
36 views

Which advanced data structure to use?

For range queries on a subarray [L,R] , I want to find all the indices of successive maximums from left to right within O(log(R-L+1)), excluding index "L". I know using segment trees I can ...
0
votes
0answers
15 views

How to pick a random index in an array based on the index's value?

While solving a problem on leetcode, I used a heap to give the largest probable value. The problem statement is as follows: Given an array w of positive integers, where w[i] describes the weight of ...