Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [arrays]

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

32
votes
4answers
2k views

How to measure “sortedness”

I'm wondering if there is a standard way of measuring the "sortedness" of an array? Would an array which has the median number of possible inversions be considered maximally unsorted? By that I mean ...
59
votes
3answers
10k views

In-place algorithm for interleaving an array

You are given an array of $2n$ elements $$a_1, a_2, \dots, a_n, b_1, b_2, \dots b_n$$ The task is to interleave the array, using an in-place algorithm such that the resulting array looks like $$...
13
votes
1answer
424 views

Overflow safe summation

Suppose I am given $n$ fixed width integers (i.e. they fit in a register of width $w$), $a_1, a_2, \dots a_n$ such that their sum $a_1 + a_2 + \dots + a_n = S$ also fits in a register of width $w$. ...
6
votes
3answers
7k 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 ...
5
votes
3answers
4k 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 ...
4
votes
2answers
4k 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 ...
4
votes
2answers
3k 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, 8]$ ...
0
votes
1answer
1k views

Divide and Conquer majority element algorithm

The algorithm should return the majority element if it exists (majority meaning that there are $> n/2$ occurrences in the array) I came up with this linear divide and conquer algorithm, but I'm ...
30
votes
5answers
43k views

Adding elements to a sorted array

What would be the fastest way of doing this (from an algorithmic perspective, as well as a practical matter)? I was thinking something along the following lines. I could add to the end of an array ...
21
votes
7answers
7k views

One element that differs in two arrays. How to find it efficiently?

I am preparing for a coding interview and I can't really figure out the most efficient way to solve this problem. Let's say we have two arrays consisting of numbers that are unsorted. Array 2 ...
20
votes
3answers
2k views

Is there an algorithm which finds sorted subsequences of size three in $O(n)$ time?

I want to prove or disprove the existence of an algorithm which, given an array $A$ of integers, finds three indices $i, j$ and $k$ such that $i < j < k$ and $A[i] < A[j] < A[k]$ (or finds ...
14
votes
1answer
2k views

Counting inversion pairs

A classic application of divide and conquer is to solve the following problem: Given an array $a[1\dots n]$ of distinct, comparable elements, count the number of inversion pairs in the array: pairs $(...
12
votes
3answers
8k views

Finding the element that occurs the most in a very large file

I've heard this interview question asked a lot and I was hoping to get some opinions on what good answers might be: You have a large file 10+ GB and you want to find out which element occurs the most, ...
4
votes
1answer
3k 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], ...
18
votes
1answer
868 views

Saving on array initialization

I recently read that it is possible to have arrays which need not be initialized, i.e. it is possible to use them without having to spend any time trying to set each member to the default value. i.e. ...
4
votes
1answer
96 views

Maximum subarray of bounded length

I'm giving an array $A[0..n-1]$ and an integer $w$. The goal is to find indices $i,j$ that maximize $$\Phi(i,j) = A[i] + A[i+1] + \dots + A[j-1],$$ subject to the requirements that $0 \le i \le j \...
8
votes
2answers
511 views

Detecting overflow in summation

Suppose I am given an array of $n$ fixed width integers (i.e. they fit in a register of width $w$), $a_1, a_2, \dots a_n$. I want to compute the sum $S = a_1 + \ldots + a_n$ on a machine with 2's ...
3
votes
2answers
224 views

Sublinear query time for the $i$th element of an array after some additions?

We are given an array $A[1..n]$ of integers, and an array of 3-tuples known as queries. The query tuples $(i,j,v)$ denote additions of an integer $v$ to the subarray of $A[i..j]$. I'm interested in ...
2
votes
2answers
148 views

Finding the maximum of a bitonic sequence

Given to us is an array $B[1],\ldots,B[n]$ as input, which satisfies the following property: there exists a special index $i^* ∈ \{1, \dots , n\}$ such that $$B[1] < B[2] < \dots < B[i^*− 1] &...
0
votes
2answers
163 views

1D Peak-finding problem, how to derive the formula?

I couldn't find a good answer to how this formula was derived for the divide and conquer algorithm in a 1D Peak-Finding problem. About the problem Basically, there's an array of numbers and we want ...
6
votes
1answer
2k 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 ...
5
votes
5answers
3k 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 ...
5
votes
1answer
435 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 ...
3
votes
7answers
4k 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 ...
3
votes
1answer
5k views

How to prove that average complexity is N/2 for linear search in the unsorted array [duplicate]

All tutorials on algorithms show the complexity for the linear search in the unsorted array in the average case as N/2. I understand that the average case means the ...
2
votes
0answers
92 views

Array counter with mimimum find

I need to implement data strucure such as array, but with the following interface: GetMin() - Returns the minimum from the array IncRight(index) - Increases all values from specified index to the end ...
2
votes
1answer
119 views

What is total work of managing the dynamic array and why is it the same as for fixed array - O(n)

I'm reading the chapter on dynamic arrays in The Algorithm Design Manual book. Here is the excerpt from the book: Actually, we can efficiently enlarge arrays as we need them, through the miracle ...
2
votes
3answers
284 views

Why shuffling by picking random position in all array instead of a part is not correct

There is a famous problem to generate a random permutation of elements in an array - it's called shuffling. My understanding of that problem is that I have to put every element in an array into a ...
1
vote
0answers
730 views

Longest Increasing Subsequence

I got no responses on stackoverflow, so I'm asking here: How useful is the LIS (Longest Increasing Subsequence) problem in tackling other CS problems? There are a few algorithms, using patience ...
1
vote
2answers
65 views

Find a recurrence relation for merging of sublists of an array

There are $\log n$ sublists each of size $\frac{n}{\log n}$. Write a recurrence relation for merging these lists into an $n$ element list. My Approach Let $m = \log n$. Then, $T(m) = 2T(m/2) + O(n)$,...
0
votes
1answer
42 views

Job scheduling approximation

In the course notes for Stanford MS&E-319: https://web.stanford.edu/class/msande319/lec1.pdf Lemma 5 is given as: The approximation factor of the modified greedy [scheduling] algorithm is 4/3....
0
votes
3answers
170 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 ...
0
votes
1answer
84 views

For each $i$, find minimal $j>i$ such that $A[j]>A[i]$ [closed]

I have the following problem: Given an array $A$, I need to construct an array $B$ such that $B[i]$ is the minimum $j>i$ such that $A[j]>A[i]$, or Null if no such $j$ exists. For example,...
0
votes
1answer
222 views

What is `wasted space` parameter and why is it O(n) for a linked list

I'm reading a book on data structures and there is a comparison between linked list, array and dynamic array. The parameter name is wasted space. Here are the values: \begin{array}{cc} \text{...
0
votes
4answers
7k 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 ...
0
votes
1answer
198 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. ...
-1
votes
2answers
113 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 ...