Questions tagged [arrays]

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

Filter by
Sorted by
Tagged with
2
votes
2answers
187 views

Remove x last elements of an array and reinsert them before position y

I am looking for an algorithm to move a subarray in before an element (which is not part of that subarray) in the same array where the last element of the subarray is the last element of the array ...
1
vote
1answer
41 views

Return the subset with smallest cardinality of an array whose elements sum to at least a given value

Suppose we are given an array $A[1\ldots n]$ and a value $C$. Is there an algorithm with linear expected runtime that can produce an array that is the subset with smallest cardinality of $A[1\ldots ...
0
votes
1answer
37 views

Check subset sum for special array

I was trying to solve the following problem. We are given N and A[0] ...
3
votes
1answer
50 views

How to answer multiple queries efficiently?

I am given a $N$-length integer array. For each integer, I am given 4 values: $$[\mathit{left},\mathit{right},t,\mathit{value}]$$ $$1\leq \mathit{left},\mathit{right},t\leq N$$ For each query, I ...
3
votes
2answers
66 views

How to sort a large list of elements where everything is sorted but k elements?

Assuming the list is very large, and $k$ is very small, what's the fastest algorithm to sort this list?
1
vote
2answers
35 views

Algorithm Design: Efficient O(n) algorithm to get the ith to jth largest elements in an array

I am trying to design an efficient algorithm that retrieves the ith to jth largest elements in an array. For example, if the following array is the input: ...
1
vote
0answers
31 views

Integer-array indexing (e.g. numpy.take) as function composition: where can I find more resources?

For context, one of Numpy's features is that an an array of integers can be passed as an index to an array, and this selects values at all of the specified positions, in any order with possible ...
0
votes
0answers
41 views

Is there an algorithm to compress a string array represented as pointers to a long string to pointers with a compressed version of the long string?

In a program I am writing, I represent an array of strings as a long string and have pointers point at the various substrings to present my array. E.g. ...
3
votes
1answer
67 views

Why is LinkedList useful?

If you implement a stack with a dynamic array-based with LinkedList you need more memory than with a dynamic array, and with dynamic array for insert in amortized cost is O(1), so the advantage of the ...
0
votes
0answers
25 views

Minimum amount of rectangles to create a 2-dimensional matrix

From this codegolf question. Consider an $r$ by $c$ matrix of nonnegative integers, called $M$. You also have a zero matrix of the same dimensions, called $N$. A "move" consists of replacing a ...
1
vote
3answers
88 views

Why is heap insert O(logN) instead O(n) when you use an array?

I am studying about the arrays vs heap for make a priority queue For check the heap implementation I am reviewing this code: Heap , but I have the following question. Heap is based on array, and ...
0
votes
0answers
33 views

Finding the rightmost element in an array of duplicate elements using binary search

i was reading Binary Search in the wikipedia and i came across this part of 'rightmost index of an element in an array of duplicate elements'. i understood the process of determining the leftmost ...
0
votes
1answer
28 views

Filler Algorithm

I am curious to know if there is an algorithm that, given an array of decimals and integers, and given an integer, returns a sequence in descending order, composed of those numbers of the input array ...
1
vote
1answer
40 views

Counting common values in two arrays

given two arrays of integers A and B of size m, with values in the range [-n,n]. I want an algorithm to count how many common values are in A and B , if a value is repeated we only count it once , ...
0
votes
1answer
61 views

Find pair with maximum Appeal value

Find pair with maximum Appeal value. Input: Array Output: index {i, j} ( i = j allowed) with maximum Appeal Appeal = A[i] +A[j] + abs(i-j) Example 1: Input: [1, 3, -1] Output: [1, 1] Explanation: ...
2
votes
2answers
77 views

What is the meaning of uniform distribution of elements in an array?

I was going through the concept of Interpolation search and it stated that when the elements are "uniformly distributed", it takes O(loglogn) to search an element using interpolation search. Can ...
2
votes
1answer
62 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
60 views

How to remove objects from an array most efficiently?

I am wondering if I can rearrange an array faster when I would like to delete more than one object. You are given a List: 1 2 2 3 4 5 7 And now you want to delete every "2" in the list. So what I ...
2
votes
1answer
57 views

Range of each building in array

I have two arrays, X and H, where X is sorted. X[i] represents the coordinate of building i. Y[i] represents the height of building i. If building i collapses, all buildings in the interval [ X[i]+1, ...
0
votes
0answers
18 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 ...
-1
votes
2answers
34 views

Any array takes at least log(n!) compairs to be sorted [duplicate]

I have to prove that there is no comparison based algorithem that can sort a randomly given array in less than log(n!) steps. Lets say the array has 5 elements, it is impossible to sort it (using ...
0
votes
1answer
62 views

Is there an O(1) solution to find the kth-smallest element in an implicit min-heap?

I know this would be an O(k log n) operation on a traditional heap, and I know there are ways to maintain Kth-smallest over a stream of inserts/deletes for constant-time access... My question though ...
2
votes
1answer
108 views

How to search an almost sorted array faster than O(n) time?

Assume a 1-indexed array A[1...n], containing integers, where A[1] ≤ A[n]. The contents of the array have the following property : for 1 ≤ i < n, |A[i] − A[i + 1]| ≤ 1. Develop an efficient ...
1
vote
1answer
69 views

Is there a linear-time algorithm to determine if an array has duplicate entries that uses only constant extra space?

Determining whether or not an array has duplicate entries has two straightforward solutions: Build a hashset of entries, then search for elements in this hashset. This takes $\mathcal O(n)$ time and $...
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 ...
3
votes
3answers
56 views

Why is subarray $A[p..k-1]$ empty when $k=p$?

I'm working through a proof of correctness for merge sort. I'm given a loop invariant for a for loop, which makes reference to a subarray $A[p..k-1]$. During the initialization step of the ...
0
votes
0answers
49 views

Number of comparisons in array where each element appears n/k times [duplicate]

Given an array of $n$ elements with $k$ distinct elements, each appearing $n/k$ times, how can I show that the number of comparisons to the sort the array in the worst case is in $\Omega(n \log k)$?
2
votes
1answer
57 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 ...
1
vote
0answers
50 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
2answers
45 views

Check if two separate ranges have some number in common

We are given two permutations: A of size N and B of size M. We need to process Q queries, each query is given by two ranges, one subarray range in permutation A and one in B. We should check if there ...
1
vote
1answer
26 views

What is an array that can be iterated circularly an infinite amount of times called?

I have a feeling that the answer is either a "circular linked list" or a finite state machine, but the answer is probably a circular linked list.
2
votes
2answers
42 views

Copying items in arrays while checking their indexes

Array $P$ of length $n$ is a permutations of $\{0, ..., n-1\}$ Write a code, which would in $O(n)$ create an array $R$ of length $n$, so for values $x_i, x_j \in P$, $R[x_i] < R[x_j]$ if $...
1
vote
1answer
54 views

If an array is full of the same integer, like 0s or 1s, are they all the peak of the array?

I am learning the MIT course Introduction to Algorithms. The professor is saying In particular, as an example, position 2 is a peak if, and only if, b greater than or equal to a, and b greater ...
1
vote
1answer
29 views

Kth smallest element in an arra [duplicate]

What would be an efficient method to find the kth smallest element in an array with worst case time complexity being $ O(n) $?
1
vote
2answers
67 views

2D peak reasoning to move to a half

You have a 2D integer matrix given. An element is a peak element if it is greater than or equal to its four neighbors, left, right, top and bottom. For example neighbors for A[i][j] are A[i-1][j], A[i+...
2
votes
1answer
56 views

How to reduce number of move operations in an array?

Say I have an array of numbers, e.g. [0, 1, 2, 3, 4, 5] and I want to end up with an array, e.g. [2, 1, 4, 0, 5, 3]. At my ...
-1
votes
1answer
96 views

Is there any way to find the nodes in the each subtree of each node having distance equal to height of the subtree?

We are given a tree of N nodes from 1 to N where node 1 is the root of the tree. For each node i from 1 to N, you have to find the numbers of nodes which are in the subtree of i and are at distance ...
1
vote
1answer
46 views

Why finding the difference between the adjacent elements of the array to find the maximum difference?

I want to understand a tricky method to find the maximum difference between two elements such that larger element appears after the smaller number. I found easy solution keeping track of the minimum ...
0
votes
1answer
48 views

The time complexity of finding the kth smallest number using buckets

I've implemented kth smallest number using buckets representing the current nibble value of each element in the array where ...
0
votes
1answer
65 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
1answer
644 views

Partition array into k subsets

We are given an array and a number K. Partition array into K subsets such that let MaxSum be the maximum sum of among subsets. We have to minimize summation =$$\sum_{i=1}^{k}MaxSum-sum(i) $$ Is ...
7
votes
2answers
486 views

Find a point shared by maximum segments

Given: $N$ segments (arrays) of ordered integers, integers could be from $-K$ to $K$. Example: ...
4
votes
1answer
191 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 \...
2
votes
0answers
63 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 ...
3
votes
1answer
32 views

Finding maximum takes at least $\lceil n/2 \rceil$ comparisons

We are given an array $A$ with $n$ elements, $n \in \mathbb{N}$ and all elements are in the set $\{1,2,3, \cdots, n \}$. I want to prove that finding the maximum in $A$ (that is, outputting the index ...
2
votes
0answers
101 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
1answer
203 views

Count the number of subsets with product less than or equal to k [closed]

You are given an array $A$ of $n$ positive integers, you have to find the number of subsets the product of whose elements is less than or equal to a given integer $k$. Is there an efficient algorithm ...
3
votes
1answer
59 views

Efficient algorithm to replace list of integers with nearest bigger element

The original question was in the context of an array, but I just used a list without changing the length for easier debugging purposes of toString(). Given an ...
3
votes
1answer
53 views

Using bit arrays to solve crossword puzzles

I have read Crossword Puzzles and Constraint Satisfaction by Connor, Duchi and Lo and I am trying to implement this variation of crossword solving algorithm. I can't understand the bit array data ...
2
votes
1answer
307 views

Time complexity to find Median of Medians

I recently wrote my Grad school Admission test few days back and the following question appeared in the test. There are 'n' unsorted Arrays : A1, A2, ...., An. Assume that 'n' is odd. Each of A1, A2, ....