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

learn more… | top users | synonyms

0
votes
0answers
1 view

Is this an advantage of using an array to implement an ADT bag?

Is it true that the client has control over the size of the bag in this case? Because I know arrays are fixed which means you could set a specified size so that the client can't go over it.
0
votes
1answer
10 views

What is a limitation of using an array concerning capacity?

Is it that you need a separate method to expand the array whenever it goes over the capacity?
3
votes
3answers
65 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
64 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
240 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
35 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
74 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
47 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
138 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
63 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
24 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
549 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
73 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
50 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
48 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
55 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
106 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
110 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
62 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
102 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
27 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
39 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
566 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
25 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
192 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
8 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
93 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
111 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
108 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
156 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
37 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 ...
1
vote
1answer
63 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
410 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
73 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
35 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
833 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
81 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
25 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
121 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
114 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
229 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 ...
-3
votes
1answer
183 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
107 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
171 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
296 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
684 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
86 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
68 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
101 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 ...