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

learn more… | top users | synonyms

0
votes
0answers
22 views

Pseudocode for checking if two arrays contain the same elements?

I'm not so much confused as to write the actual code as I am to write the pseudocode. To determine if two arrays of the same size contain the same elements, I know you would need two for loops, then ...
1
vote
0answers
24 views

Minimum-Maximum recursive algorithm with a non-even partition, complexity [closed]

So I have been trying to find the recurrence relation of the following algorithm in order to compute its complexity. The following algorithm describes how to find the minimum-maximum element in an ...
-4
votes
1answer
80 views

Write an algorithm that finds array elements that sum up to some value [closed]

The following is a pseudo-code named PractOne. It takes a finite list A of real numbers and gives the pair ...
1
vote
1answer
52 views

What is “Oracle Access”?

I'm reading a paper for school and I have come across a passage that I don't understand. It says "If we allow the query to access the entries of the array through an oracle, it is possible to obtain a ...
0
votes
0answers
48 views

Finding longest subsegment of array having certain property

Assume we are given an Array[0,N) of N integers A [0], A[1], ... A[N-1] and a boolean function Bad(n) that examines consecutive elements A[n], A[n+1], A[n+2] for some property of "badness". For ...
5
votes
5answers
2k views

What is the best solution to find whether the sum of an array is even or odd

I was asked this question in an interview. I was not able to find a better solution than $O(n)$ which is just going over the array and finding the sum. Can it be done any better? I am not really ...
3
votes
1answer
54 views

Efficient way to calculate sum in sliding window?

Assume you have a grid as below: The square is the sliding window. I want to slide this window over all the possible position such that the window is contained in the grid (i.e the edges of the ...
0
votes
1answer
115 views

What is an ordered array? [duplicate]

I am not able to find a clear explanation about Ordered Arrays. All I know is The array is 1-ordered it is in the usual order. (For the 1st must be less than the 2nd which in turn must be less ...
1
vote
1answer
47 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 ...
0
votes
3answers
58 views

How can I keep track of the state of a sequence after rotating parts of it multiple times?

Given a sorted array 1 2 3 4 5 6 7 8 and an operation that takes the N-th element out the array and puts it in front (or rotates the first N elements to the ...
1
vote
1answer
61 views

Amortized analysis of virtual, dynamic array using potential function

You often want to implement an array $A$ where the length fluctuates over time. If at some point $A$ has length $n$, then you would like to use space $O(n)$. Consider the following: At all moments, a ...
1
vote
1answer
75 views

Implementing an interval tree using arrays?

Is it possible to create an interval tree using an array instead of the traditional pointer method? I know that for segment trees this is commonly done where the children of any element with index i ...
3
votes
1answer
49 views

Returning m greatest elements from k sorted array

We have $k$ sorted arrays, $A_1[1...n_1],...,A_k[1..n_k]$, where $n_1+n_2+...+n_k=n$. How can we get the $m$ greatest elements in running time $O(k + m\lg k)$? I have tried to use MIN-HEAP size of ...
1
vote
2answers
33 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 ...
0
votes
0answers
48 views

What is the average runtime of appending items to arrays?

It is the time of the year again in colleges for final exams and I am preparing mine as of now and I am finding myself in hot water when it comes to understanding the running times of appending items ...
1
vote
1answer
28 views

Efficient Array Normalization

I want to normalize elements in an array. The solution I found is to take the sum of the elements and divide each element with this total. Can you find more efficient way of doing this? The runtime I ...
1
vote
1answer
20 views

Algorithm to maximize $j-i$ subject to $A[j]>A[i]$

We want an algorithm that, given an array $A$ of length $n$ of integers (indexed by $A[0],A[1],\ldots,A[n-1]$, determine values $i<j$ that maximizes $j-i $ subject to $A[j]>A[i]$ (if such values ...
7
votes
2answers
568 views

Algorithm to find smallest difference in array

We want an algorithm that, given an array of length $n$ of integers, find the minimum difference between two integers in the array. One such algorithm is to sort the array and check adjacent pairs of ...
30
votes
7answers
7k views

Keeping a String Secret in (Open) Source Code

I have finished developing an app for Android and intend to publish it with GPL -- I want it to be open source. However, the nature of the application (a game) is that it asks riddles and has the ...
0
votes
2answers
41 views

Recursion: base case vs. small version

I'm reviewing the definition of recursion and in my notes are two questions about a recursive problem. One question asks about the base case, the other one about the small version of the problem, I ...
3
votes
2answers
108 views

match an array with a given set of arrays

We have a set of 24 distinct arrays, each array has 36 elements and each element can have one of 13 possible values. Then we're given an array X (this array is certainly part of our set) and we have ...
-1
votes
1answer
46 views

Distributing values of an array into smaller arrays with bounded sums

Take the following array of integers: [60, 45, 30, 45, 45, 5, 60, 45, 30, 30, 45, 60, 60, 45, 30, 30, 60, 30, 30] They need to be sorted into pairs of sub-arrays. The first sub-array in each pair ...
0
votes
1answer
217 views

Time complexity of Dynamic Array via repeated doubling

When we implement dynamic array via repeated doubling (if the current array is full) we simply create a new array that is double the current array size and copy the previous elements and then add the ...
2
votes
0answers
96 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 ...
1
vote
2answers
384 views

k-ordered array problem

An array $A[1...n]$ is said to be k-ordered if $$A[i - k] \leq A[i] \leq A[i + k]$$ for all $i$ such that $k < i \leq n - k$. For example, the array $A = [1, 4, 2, 6, 3, 7, 5, ...
0
votes
1answer
168 views

Sorted array with odd indexed elements swapped randomly [closed]

A sorted array $\mathcal{A}$ with even number of elements is given. Consider $\mathcal{A}$ be partitioned from the middle such that both parts ($\mathcal{A}_1, \mathcal{A}_2$) contain equal number ...
2
votes
0answers
127 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 ...
1
vote
1answer
40 views

Lower bound on number of comparisons needed to search for a number in a sorted 3-d array

Suppose we have an $N \times N \times N$ 3-d sorted array meaning that every row,column, and file is in sorted order. Searching for an element in this structure can be done using $O(N^2)$ comparisons. ...
1
vote
1answer
203 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
2answers
359 views

Proving the Bubblesort actually sorts

Say $A'$ is the output of $\mathrm{Bubblesort}(A)$ on an array of length $N$. To prove that Bubblesort works, we have to prove that it always terminates and that $$A'[0]\leq A'[1] \leq \dots \leq ...
2
votes
7answers
2k views

Checking if there are 2 elements in an array that sum to X in O(n lg n)

I have thought about the most useful way of checking an array for 2 elements that sum to X. The trivial solution is to check the sum of every element with every element, and the complexity of this ...
1
vote
0answers
81 views

Find the largest number of independent subarrays given an array [closed]

We are given an array and numerous subarrays. What we can do is add or multiply some element to all elements of a subarray. The subarrays are given as start index and the end index. We have to find ...
1
vote
2answers
918 views

Finding a O(n) solution to: max difference of pairs array question [closed]

I don't know an O(n) solution to the following: Given an array of n integers, find the largest difference between any two pairs in the array: however, the larger integer must have a higher index in ...
0
votes
2answers
549 views

Partition array into K subsets, each with balanced sum

Given array $A = \{ a_{1},a_{2}, ..., a_{n}\}$ and integer $k; 0 \lt k \le n$, partition array $A$ into $k$ subarrays, such that $A'_{1} = \{a_{1}, ...,a_{x}\}$ $A'_{2} = \{a_{x+1},...,a_{y}\}$ ...
2
votes
2answers
92 views

What is this hash of array data structure called?

I've created a data structure that is a hash of arrays with a special property: the hash keeps track of the combined order in which items are appended to its arrays. For example (pseudocode): ...
1
vote
2answers
59 views

Hashing a Specific Range Of a Character Array [closed]

I need to process queries to Hash various ranges of a character array. I am currently using the Arrays.hashCode from the standard java library. But the problem is that this method is too slow. Also my ...
3
votes
3answers
814 views

Number of submatrices with a particular sum

Given a $n\times n$ matrix A[0...n-1][0....n-1] where all entries are non-negative integers, and a non-negative integer K, I ...
2
votes
1answer
147 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 ...
3
votes
1answer
47 views

Term for array of identical type and different types

What is proper terminology to distinguish between an array (ordered list) data structure in which each element is of identical type/class, and an array in which each element can be different?
-1
votes
4answers
1k views

How to reverse a subarray of an array

Edit: found solution with $O(1)$ look for my answer at here I have an array of elements, and I wish to reverse the order of elements between indices $i$ and $j$. Example: Let the array contain ...
3
votes
1answer
688 views

Maximum number of inversions that can be removed by swapping two elements?

I have come across a question that is a bit hard to understand due to its wording, I may havecome up with a possible solution, but I don't know if it's correct. Can you please help me? Thanks in ...
0
votes
1answer
67 views

experimental analysis of running times in extendable table [closed]

I was given the following homework question: Implement an extendable table using arrays that can increase in size as elements are added. Perform an experimental analysis of each of the running ...
4
votes
1answer
156 views

Searching a value in a “piecewise” ordered array

If we have an array $A$ of length $N$, which is partitioned into $\sqrt{N}$ adjacent subarrays $A(i)$, each of which is monotonically ordered from $\min(i)$ to $\max(i)$ (it is known what places have ...
11
votes
4answers
3k views

How to implement two stacks in one array?

I want to begin by saying that this is NOT a homework question. I am reading Introduction to Algorithms - the famous CLRS text to become a better programmer. I am trying to solve the problems and ...
5
votes
2answers
449 views

Search for minimum in an array of $k$ monotonic subarrays

Let $A$ be an array of totally ordered elements. A subarray $A[i..j]$ is decreasing if $A[k]\geq A[k+1]$ for all $i \leq k < j$. It is increasing if $A[k]\leq A[k+1]$ for all $i \leq k < j$. It ...
9
votes
1answer
715 views

Counting number of sums from contiguous subarrays of an array

We are given an array $a[1 \ldots n]$ with all $a[i]>0$. Now we need to find how many distinct sums can be formed from its subarrays (where a subarray is a contiguous range of the array, i.e., ...
3
votes
3answers
526 views

Runtime of searching for a number in an array?

Searching for a number in an array is said to have a runtime of O(n) because there may be cases where the number doesn't exist in the array. In such cases, you'd have to have gone through the entire ...
1
vote
1answer
161 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
48 views

Constructing a Divide and Conquer Algorithm

I'm thinking of using something similar to the Merge Sort algorithm. So the recurrence running time of Merge Sort is T(n) = 2T(n/2) + n. What should I do about if n/2 is less than or equal to m, OR ...
3
votes
1answer
548 views

Lower-bound complexities for finding common elements between two unsorted arrays

I'm facing some problems that deal with finding common elements between unsorted arrays and I'd like to know whether there are well-known lower-bounds for the worst-case and, eventually, what are ...