Questions tagged [arrays]

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

59 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
423 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 ...
142 views

Sort 2D arrays so that cost of reaching new position as described at each iteration is minimized

Problem is as following: We are 8 trumpet players in an orchestra. There are for example 4 parts so there are always two players on the same part. Now, there are not always the same two players ...
1k views

Find the median of two sorted arrays of different size in O(min(log(n),log(m)) complexity

Given two sorted arrays of length m,n, how do I find the median of the union of these two arrays in O(min(log(n),log(m)) time? I've been trying to come up with an algorithm (and a proof) for several ...
613 views

Algorithm for solving rectangle puzzle

Early note: This is not homework. I simply regularly create ideas in an attempt to teach myself a language. For what it's worth I'll be using Javascript for this. That said, I haven't been able to ...
5k 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 ...
90 views

How to find the top k pairwise product of in an array of integers?

Input: An array $a$ of integers $[a_{1}, \cdots, a_{n}]$, and a positive integer $k$. Output: The the top-k products of pairs in $a$. Example: $a = [7,6,5,4,3,2,1],k=3$ , output $(42,35,30)$, with ...
724 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 ...
56 views

Thought process for the following problem?

We are given a 1-d array and we have to return the smallest array attainable after removing all the continuous same numbers. We can only eliminate those numbers which repeat continuously more than or ...
59 views

Minimum number of deleting palindromes to delete whole string

Let's say we have given array $A$ of size $n$. Our goal is to delete the whole array with minimum steps. In one step we can choose substring (consecutive elements from the string) and delete it only ...
85 views

Min no.of operations required to convert an array to which it should contain elements of equal frequency

I have come across this tricky problem. An array of N elements should be converted to another array within k operations such ...
62 views

Sort arrays $A$ and $B$ of the same elements using only comparisons between an element of $A$ and one of $B$

Premise: Let $A := [ k(1), k(2), ..., k(n) ]$ and $B:=[ l(1), l(2), ..., l(n) ]$ be two Arrays where $k$ and $l$ are permutations. (What I'm trying to express: $A$ and $B$ contain the same elements in ...
39 views

Abstract Data Type

I have been studying data structures. In that I have come across topics like Array being defined as Power set of cross product of set of objects and set of natural number and list being defined as ...
57 views

Counting subarrays where each number either doesn't occur or occurs odd number of times

We have given array $V$ of $N$ integers, we want to count the number of subarrays of the array such that each elements in the subarray either doesn't occur at all, or it occurs odd number of times. ...
1k views

Given an array of integers and a value k, find the length of the longest subarray with max-gap no more than k

I'm struggling with this problem: you are given an array $A$ of $n$ integers and a number $k \in \mathbb{N} : k \neq 0$. The problem asks to find an algorithm that runs in $\Theta(n)$ that returns the ...
194 views

Understanding the Polyhedral Model

I am wondering at a high level the mathematics of the Polyhedral Model. The polyhedral model (also called the polytope method) is a mathematical framework for programs that perform large numbers of ...
78 views

Counting inversions with index constraint

I have a series of line segments $l_i=(a_i,b_i)$ with $i=1,2,3...n$ $a_i$ and $b_i$ are their starting and ending points coordinates in $x$ axis. The question is how to find a algorithm that is ...
184 views

53 views

find a values of a array members

We have Some big hashed array of data with boolean values, we know keys, but don't know values. Oracle who have input of array of keys and can tell how much of them are ...