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

learn more… | top users | synonyms

-4
votes
0answers
21 views

software development [closed]

Write a Java program which contains your own function(s) to calculate the solution of the problem given below then print which choise is true. There are 4 doctors and 7 nurses. How many 5-person teams ...
0
votes
3answers
117 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
83 views

Time and space complexity of removing duplicates in a sorted list

Is it possible to delete duplicates from a sorted array in $O(\log N)$ time and $O(1)$ space?
-1
votes
1answer
39 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
113 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 ...
2
votes
1answer
47 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
41 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
31 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] < ...
4
votes
1answer
64 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
28 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
94 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 ...
14
votes
3answers
437 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
31 views

Merge k sorted arrays, each one's length is double than its' previous

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 best comparison ...
4
votes
0answers
42 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

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
24 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
20 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
119 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
71 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
257 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
63 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
110 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
2answers
53 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
139 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
66 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 ...
3
votes
1answer
30 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
560 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
93 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
53 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
50 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
63 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
114 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 ...
-2
votes
2answers
70 views

Find the index of the next greatest element in the array

I know there is a stack based approach with O(N) complexity and O(N) space. Can B be created using O(1) space? Such as in place using a single loop or even some sorting algorithm ? If so, can you ...
2
votes
1answer
173 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 ...
0
votes
1answer
30 views

lower bound of checking if in array are two different elements [closed]

Considering the lower limit to the problem of checking whether the array are only the same number via comparisons. And thnik about $ n-1 $. Consider the diagram hasse. This diagram must be consistent ...
2
votes
1answer
41 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 ...
3
votes
1answer
653 views

What is a partially sorted array?

I come across this definition but it's not so clear for me ! An array is partially sorted if the number of inversions is less or equal a constant times the array length. if array length is N ...
0
votes
0answers
27 views

Fast Raytracing Algorithm or Alternative needed

I have a grid that shows the world and its coastlines. An excerpt from the area around the UK is shown here From an arbitrary origin point anywhere in the ocean, I want to find those coastline ...
2
votes
2answers
226 views

What's a uniform shuffle?

What does it mean exactly a "uniform shuffle" algorithm ? Is this method considered a uniform shuffle ? ...
0
votes
0answers
9 views

Find all pairs of matching elements in two arrays [duplicate]

I have two arrays A & B, each with an element from one that corresponds to the other (for each a in A there is a b in B it corresponds to). And I don't want to brute-force check them all in ...
6
votes
1answer
102 views

How do arrays work “under the hood”?

In some languages (such as C), arrays seem very simple to me. When allocating memory for these, all you need to do is pick a starting point in memory and then allocate the next ...
2
votes
2answers
122 views

Find the number of values between i & j(given as input) in an unsorted array in O(1) time

Given an unsorted array $A$ of $n$ numbers and inputs $i$ and $j$, can we find the number of values $i<k<j$ in $A$ in O(1) time complexity by doing some preprocessing? An additional requirement ...
-1
votes
4answers
139 views

What is an array of arrays called when all arrays have the same size?

If I have an array a of arrays, in many languages they may have different size. Is there a word for an array of arrays where all the arrays have the same length? Edit: An array of arrays may have the ...
2
votes
2answers
171 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, ...
-1
votes
1answer
40 views

Find minimum value at each index after queries which tell you minimum value over a range [duplicate]

Assume that initially in array each element has infinity as value. Now M queries are input of the type l r x. Here l to r is range where value need to be updated if a[i]>x where l<=i<=r. and ...
2
votes
1answer
67 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 ...
1
vote
1answer
563 views

Why does Kadane's algorithm solve the maximum sub-array problem?

I've tried to solve a exercise 4.1-5 in algorithm book "Introduction to algorithms". it is about Maximum sub-array problem, which is an algorithm that determines the greatest sum of sub-array A[i], ...
3
votes
1answer
76 views

Succinct bounded-sum array with $O(1)$ access

Assume we have a $n$ sized integer array $A$, and that we know that $\sum_{i\in[n]}A[i] \le M$. Assume we are using the RAM model with $\Theta(\log n)$ sized memory words (which can be read / written ...