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
7
votes
0answers
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 ...
6
votes
1answer
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 ...
4
votes
0answers
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 ...
4
votes
0answers
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 ...
4
votes
1answer
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 ...
3
votes
0answers
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 ...
3
votes
0answers
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 ...
2
votes
1answer
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 ...
2
votes
0answers
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 ...
2
votes
0answers
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 ...
2
votes
0answers
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 ...
2
votes
0answers
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 ...
2
votes
0answers
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. ...
2
votes
3answers
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 ...
2
votes
0answers
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 ...
2
votes
0answers
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 ...
2
votes
0answers
184 views

Given An Array of Intervals, Find the Supersets

Suppose we have the following array of pairs representing start and end indices within an array. Think of them as an interval. I'll be using this term from now on. $[\left\{1,3\right\},\left\{4,9\...
2
votes
0answers
93 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
0answers
105 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 ...
2
votes
1answer
58 views

Find the nearest sum to a given number of two elements in sorted matrix

Given a sorted $n\times n$ matrix $A$ of real values. That is $a_{ki}<a_{kj}$ and $a_{it}<a_{jt}$, when $i<j$. Propose and algorithm, finding two elements of this matrix with the sum nearest ...
1
vote
0answers
39 views

Algorithm to save state of array as it changes

There's an array which changes with every iteration, i.e., an element is added or deleted in every iteration. I have to save the "state" of the array for every iteration, which would later be ...
1
vote
1answer
24 views

Sequential subsequence removal with arbitrary predicate

I want to extract sub-sequences from a sequence of float values. The "scale" and range of these values is arbitrary (as I can manipulate it at will) but the "shape" is consistent. For a visual ...
1
vote
0answers
48 views

Is it possible to write a fully-decidable type system for the J language?

I'm experimenting with the J array language, a dynamically-typed array language with mutable assignment, subtyping, and function overloading (just like traditional APL). It is unclear to me whether ...
1
vote
0answers
30 views

Recurrence Relation for Column Major Form of multidimensional array

A two dimensional array is stored in column major form in memory if the elements are stored in the following sequence $$A[0][0] A[1][0] A[2][0]...A[n_1-1][0] ... A[0][1] A[1][1] ... A[n_1-1][1] .... A[...
1
vote
1answer
204 views

Array subset division with equal sums

Today I stumbled upon a problem which looked like the partition problem but certainly is different. Given array of positive integers, guaranteed to not be divisible into two continious subsets of ...
1
vote
0answers
94 views

How does prefix summing the count histogram in counting sort result in an array of output indices?

My implementation of counting sort is based on the description I found here. I've also included my code in this REPL, but here it is: ...
1
vote
2answers
120 views

FInding the combination with the least number of elements from and array of integers, given an integer sum

I'm doing and assignment where the problem is to find the combination with the least number of elements form an array of integers, given an integer sum. I have solved this using a gready algorithm ...
1
vote
2answers
28 views

Generate Evenly Distributed Pattern Based on Weights

I have an array of items $A = \{A_i\}, i \in I $ with integer weights $W_i, i \in I$. I need to build a function $f: I \rightarrow A $, that produces evenly distributed patterns of array elements ...
1
vote
0answers
21 views

How to chose the condition for expand in hash-table?

How can I chose the condition for expanding of the array in chain-hashing if I want that given some cell (that contains elements) , the number of cells that I need to move about them is O(1) until the ...
1
vote
0answers
225 views

Online algorithm to find shortest subarray containing all k-elements

We have given array of $n$ integers in the range $[1, k]$. We want to design algorithm that can modify the array and also find the length of the shortest subarray containing at least one of each ...
1
vote
0answers
1k views

To find median of k sorted arrays of n elements each in less than O(n*k*log(k))

How to find median of k sorted arrays each of length n? Note that total elements would be n*k. I know it can be done in O(n*k*log(k)) using merge technique. I am looking for a better time efficient ...
1
vote
0answers
402 views

Algorithm to split an array into minimal number of subarrays where sum of their elements is less than or equal a given one

Title of the question pretty much summarises the question. Here is a concrete example of what I'm trying to achieve with no success. Let's say we have a sorted list (but sorted is not a requirement) <...
1
vote
0answers
127 views

Maximize the minimum element

We have an array of $N$ positive elements. We can perform $M$ operations on this array. In each operation we have to select a subarray(contiguous) of length $W$ and increase each element by 1. Each ...
1
vote
0answers
129 views

Representing multisets by a bit vector

What would be the most space-efficient way to represent a multiset (a set that can contain duplicates) using a (static) bit string (bit vector, bit array, etc.)? All of the elements in the multiset ...
1
vote
0answers
72 views

Create an array minimizing sum of square deviations to another array

Problem Let y be an array of float numbers (of length $n$) bounded in the range [0,1]. I am trying to compute the array x that ...
1
vote
0answers
607 views

Can partial sums of a counter array be computed in O(log n) time?

Let $A[1 . . . n]$ be a given array of $n$ integers, where $n = 2^m$. The following two operations are the only ones to be applied to A: Add(i, y): Increment the value of $A[i]$ by $y$. ...
1
vote
0answers
346 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 ...
1
vote
0answers
756 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
1answer
112 views

Algorithm to find out the number of times a number occurs consecutively in an array in a range specified

I have an array say 8 3 5 4 4 4 4 4 3 2 7 11 12 7 7 7 7 1 2 total =17 elements now you are given a range say [2,11] both included ,now you have o find out the ...
0
votes
0answers
17 views

Linearithmic solution to finding closest pairs in an array of N elements

I am reading Algorithms 4ed by Sedgewick and Wayne. I came across this algorithm design question that asks the following: Write a program that given an array of N integers, finds a closest pair: two ...
0
votes
1answer
58 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
0answers
51 views

Variable bytes (bit arrays) and flipping single bits?

My interest is strictly theoretical at this point, but ultimately applied. Is there any problem, theoretically, with defining a byte with m bits, and flipping single bits to connote T/F for a given ...
0
votes
0answers
177 views

Analysis of finding the k-th largest element in a subsegment of an array

Given an array $A$ of length $N$. There are $Q$ queries, each queries will be in the form ...
0
votes
0answers
25 views

Minimum give away on performance based queue?

I'm trying to solve algorithm problem, so far no luck Lets imagine A is an employer and there are N employee currently on line (queuing) for receiving their paycheck of the month, and each of the ...
0
votes
0answers
223 views

How to prove the correctness of inside-out shuffle algorithm

I've read this similar question How to prove correctness of a shuffle algorithm? and I understand the answer. However I still couldn't figure out how to apply that inductive proof to a similar shuffle ...
0
votes
0answers
328 views

Interleaving first and second half of an array of even length in place

If A is an array with the following elements: $$ a_1,a_2,...,a_n,b_1,b_2,...,b_n $$ How to shuffle A to form: $$ a_1,b_1,a_2,b_2,...,a_n,b_n $$ with minimal swaps and using no additional space? I ...
0
votes
0answers
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 ...
0
votes
0answers
154 views

Is important for `Fisher–Yates shuffle` algorithm to generate random numbers in the sequential increment

This is a follow-up question to the Why shuffling by picking random position in all array instead of a part is not correct. I understand if I pick random numbers from all the range for 4 numbers every ...
0
votes
0answers
227 views

Sorting an array where half of the elements are at their correct position

By the statement of the question i am trying to generalize the structure of the array.for me Being at their correct position means they can't be shifted. I tried to come up with a few examples and ...