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

learn more… | top users | synonyms

1
vote
1answer
50 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
56 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
66 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 ...
-1
votes
1answer
29 views

Printing the array elements sorted by repetition [closed]

I just can't figure this question out: Given an array of N elements, its values range are from 0 to 100. Write a function that prints the array's elements sorted by repetition. Time complexity : ...
2
votes
1answer
80 views

What is a contiguous subarray?

What is a contiguous subarray? I have tried searching online and have found pages about solving the largest contiguous subarray problem but none with a definition or explanation of what contiguous in ...
1
vote
0answers
16 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 ...
2
votes
0answers
20 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 ...
1
vote
2answers
28 views

the convention for declaring arrays in pseudocode

I have a very simple question. What is the right standard convention to use for declaring arrays? I understand that for a simple declaration of a variable as an integer, this is the convention: ...
0
votes
0answers
39 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
54 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
90 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
59 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
52 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
78 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
183 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
54 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
62 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
71 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
88 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
50 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
34 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
51 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
30 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
25 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
662 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 ...
31
votes
7answers
8k 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
44 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
116 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
48 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
242 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
101 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
447 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
182 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
149 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
231 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
425 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
91 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
1k 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
658 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
1k 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
161 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
50 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
706 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
68 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 ...