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

learn more… | top users | synonyms

1
vote
1answer
75 views

Finding a match in two collections

Let $A$ and $B$ be two one-dimensional, finite collections of unsigned integers (e.g. arrays). Furthermore, $card(A) = a < b = card(B)$. Both collections are sorted in ascending order. There is at ...
3
votes
1answer
77 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}\...
0
votes
1answer
39 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 ...
-1
votes
0answers
29 views

Find number of pairs [duplicate]

I have an array A of integers. I want to find possible number of pairs of non-intersecting sub-array which don't have any element common in them. For example A={1, 2, 1, 2} then correct subarrays(1-...
0
votes
0answers
18 views

Dynamic Modelling improvement suggestions

I'm encountering a dynamic modelling problem. I've tried a lot of methods but it seems that all of them are of time complexity O(MNK), like the basic algorithm. I wonder if any guys can make some ...
2
votes
1answer
30 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 ...
2
votes
2answers
77 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
0answers
36 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
votes
1answer
60 views

The longest subarray sum divisible by $5$ in $O(n)$ time

Given an array of non negative integers Find the longest continuous sub array which it's sum is divisible by 5. For example if the array is: [1,3,9,2,1,5,0,1] A continuous subarray which it's ...
1
vote
1answer
33 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?
0
votes
1answer
38 views

Taking the modulus of 2 arrays [closed]

I'm putting together a primality tester for large numbers. When the numbers were smaller things were more straightforwards. I got refined it to a point where I could quickly test any number within the ...
3
votes
1answer
61 views

Why does merging two sorted arrays take 2N - 1 comparisons?

A friend of mine asked me a question on how to prove that merging two sorted arrays requires at least 2N - 1 comparisons Prove that merging two sorted arrays of N items requires at least 2N-1 ...
0
votes
1answer
28 views

Is better than O(n^2) possible for getting pairs that sum to a multiple of 10?

Is it possible to solve a problem with a worse case less than $O(n^2)$, when the input is an an array of numbers and the output is all pairs that sum to a number divisible by 10? for example ...
4
votes
0answers
118 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 ...
1
vote
0answers
18 views

Get the max difference in an array for each day in nlogn [closed]

So I'm having trouble figuring out a solution to this question. You’re a financial analyst, and have another stock market problem to solve. The input is A, ...
0
votes
3answers
306 views

Find a weighted median for unsorted array in linear time

For days, I'm trying to figure out, whether it is possible to find an item in array which would be kind of weighted median in linear time. It is very simple to do ...
-1
votes
2answers
100 views

Time and space complexity of removing duplicates in a sorted list [closed]

Is it possible to delete duplicates from a sorted array in $O(\log N)$ time and $O(1)$ space?
-1
votes
1answer
94 views

Find all possible subset pairs in an array having equal average

Given an positive integer array with distinct elements, find all possible subset pairs having equal average. How to do this ? Example: arr={5,10,6,7} Ans: {7},{5,6,10} Exp: average of first subset=7 ...
3
votes
2answers
116 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....
2
votes
1answer
49 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, ...
1
vote
0answers
47 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$. ...
-2
votes
1answer
37 views

Best search in Heap Array

Can someone give me the best search algorithm in a max heap? In particular simply implemented as an array. I knew it has complexity of $O(N)$ but it can be done better. For example, if $A[i] < \...
1
vote
2answers
39 views

How to prevent deletion in an array in the B method

I have created a very basic model of an array list in the B method as shown below ...
4
votes
1answer
66 views

Sorting array with at most two inversions

I have created an algorithm to sort an array of size $n$ with at most 2 inversions with exactly $n$ comparisons in the worst case. I have no idea how to prove that it is optimal in terms of the ...
1
vote
1answer
14 views

Generating integer vectors sorted by total weight [closed]

I am trying to implement an algorithm that finds the key of the RC4 cipher from the inner permutation. For each key byte I have several options, each with different weight. Is there any way, to test ...
0
votes
1answer
29 views

Running Build-Heap Algorithm on given numbers

I don't fully understand this build-heap function. Lets assume we have array 3, 4, 5, 13, 16, 32. It seems like we swap the parent when it is less than the current A[j] but which number does the ...
0
votes
1answer
120 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 ...
15
votes
3answers
567 views

Largest sum divisible by n

I asked this question on StackOverflow, but I think here is a more appropriate place. This is a problem from Introduction to algorithms course: You have an array $a$ with $n$ positive integers (...
0
votes
1answer
56 views

Merge k sorted arrays of exponentially increasing lengths

I've seen many answers to merge identical-sized arrays, but haven't seen the answer to this question yet. Given $A_1, A_2, ..., A_k$ sorted arrays where $|A_i| = 2^i$, what is the most efficient way ...
4
votes
0answers
62 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
82 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 ...
0
votes
2answers
27 views

Sum of Maximum of continuous blocks of length k

Given a array of N elements and a number k, then find the sum of maximum of a all continuous blocks of length k? Examples : A = {2,5,2}, k = 2, Max for 1st block = 5, 2nd block = 5, So sum is 10. A ...
0
votes
1answer
33 views

What is a limitation of using an array concerning capacity? [closed]

Is it that you need a separate method to expand the array whenever it goes over the capacity?
4
votes
3answers
176 views

How do I find the max and min value of an array in 3n/2−2 comparisons?

So I'm using this method to find the min and max value of an array simultaneously where I split the array into n/2 and n/2 parts. I then keep splitting each part until I have either a pair of numbers ...
5
votes
1answer
74 views

Finding a small element in a changing array

Consider having an integer array $A$ with $n$ elements, in addition to any data structure you like. The array is initialized to zeros. The goal to to support two operations: ...
5
votes
1answer
265 views

From Guido's essays, how does this function avoid quadratic behavior in a string concatenation algorithm?

I am reading one of Guido van Rossum's essays on optimization in Python. We are interested in converting a Python list of integers to their character equivalents. Here's the straightforward ...
1
vote
1answer
81 views

Number of submatrices, of a base matrix derived from an array, with a particular sum

Given an N sized array A of unsorted integers and an integer K, derive a square matrix M of order N where $ M_{ij} = A_i * A_j $, and return the number of sub matrices of M where the sum of all of its ...
3
votes
1answer
251 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 ...
0
votes
1answer
49 views

Can I speed up Insertion Sort by using a tree for finding insertion positions?

I want to implement an insertionSort-algorithm. Let's say I have these pseudocode. ...
4
votes
2answers
58 views

What are GPU arrays?

I came across the Python library libgpuarray and was reading about it but could not really understand what a GPU array is and why do we need it? What is the difference between a normal array and GPU ...
6
votes
1answer
143 views

Sum of all products of subarrays

For any three-dimensional array $A$ of size $n_1 \times n_2 \times n_3$ let $P(A)$ be the product of all its elements, i.e. $$P(A) = \prod_{i_1 = 1}^{n_1} \prod_{i_2 = 1}^{n_2} \prod_{i_3 = 1}^{n_3} ...
3
votes
1answer
70 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,...
3
votes
1answer
31 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$ ...
4
votes
1answer
564 views

Matrix Max in less than O(n)

I am attempting to find the maximum value in a matrix (or 2d array) and want to find it in less than O(n) time. The easiest way, which results in O(n) run time, is an element wise search. If a better ...
3
votes
2answers
103 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 ...
1
vote
1answer
56 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}$ ...
3
votes
0answers
52 views

Does the concept of the array pre-date physical computer memory implementations?

Does the concept of the array (a sequence of equally-sized elements accessible in O(1) time, occupying O(n) space) pre-date physical computer memory implementations? I am trying to gauge whether ...
1
vote
1answer
66 views

Sorting array with two elements - in place and minimal number of comparisons, lower bound

Algorithm must be in place. I would like to find lower bound for comparison algorithm. Algorithm will sort array with only two elements - without loss of generality let assume that there are only $1s$ ...
1
vote
1answer
109 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 ...
0
votes
3answers
120 views

How do I sort these elements in O(n) time?

So let's say I have an array of elements where each of the values can range from 0 to $n^2-1$. I'm trying to make an algorithm to sort this array in O(n) running time and I was thinking of using radix ...