# Questions tagged [arrays]

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

426 questions
Filter by
Sorted by
Tagged with
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 ...
700 views

### How can merging two sorted arrays of N items require at least 2N - 1 comparisons in every case?

The HW question, on page 362 of Data Structures and Algorithms in C++: Fourth Editionby Mark Allen Weiss, reads as follows: Prove that merging two sorted arrays of N items requires at least 2 * N - ...
8k views

### Find maximum element in sorted arrays in logarithmic time

Been stuck on this for a while, would really appreciate some help: Suppose you are given an array A[1...n] of sorted integers that has been circularly shifted k positions to the right. For example, ...
512 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 ...
4k views

74 views

### Is it possible to solve this problem in less than n^2 time without using additional space?

Here's the problem: Given an array array containing integers, maximize array[i] + array [j] + |i - j| where i and j both range ...
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 ...
119 views

### Finding a '1' cell with a '0' to its right in a binary array

Given an array of size n that holds ones and zeros I need to find an index of a 1 cell that has 0 to his right (in then next ...
970 views

### what is actually a circular array and representation

There are two ways to implement a circular array either take a new array of size 2N where N is the size of the initial array and copy initial array twice into that ...
290 views

### Finding duplicate in immutable array in linear time and constant space

We have a array of $N$+1 integers. The integers range from 1 to $N$. The array contains at least one duplicate. Our goal is to find one of the duplicate entries. We have the constraint that we cannot ...
180 views

### Number of Pairs in Array

so hey, I've been recently reading about the Two-Pointer algorithm that allows us to find pairs $(i,j)$ such that $a[i] + a[j] = x$ in $O(m+n)$ instead of the trivial $O(mn)$ time. I was wondering ...
6k views

### Row Major vs Column Major order access 2D arrays in programming languages

Programmers prefer accessing a 2D array in Row-Major Order rather than Column-Major Order, Why? Are there some advantages/benefits of accessing a 2D array in row-major as compare to column-major? ...
6k 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 ...
### 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 ...
I am performing an addition operation on two large binary numbers that have an equal number of bits. Both numbers are stored in an array of length $N$, which is rather large. At first I tried running ...