Questions tagged [arrays]
A sequential random-access data structure whose size can typically not be changed after creation.
356
questions
-1
votes
0answers
21 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: ...
1
vote
1answer
22 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 ...
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
votes
0answers
22 views
smallest subset with given sum
How to find the smallest subset with a given sum?
All elements are integers.
I have an array of integers and I want to find a given sum with the least number of
element possible
with both the ...
1
vote
1answer
57 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
49 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
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 ...
-1
votes
2answers
30 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
54 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
96 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
52 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
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 ...
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
2answers
41 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
41 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
53 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
25 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
54 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
55 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
76 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
30 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
47 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
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
1answer
504 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
482 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
154 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
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 ...
3
votes
1answer
31 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
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
1answer
156 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
52 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
48 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
228 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, ....
2
votes
2answers
206 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] &...
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 ...
0
votes
1answer
70 views
Applying minimax tree to this array [closed]
Please tell me how I should apply minimax algorithm to the array
$$ 15, 12, 14, 16, 11, 13$$
and make a tree?(I understand how minimax algorithm works but I can't apply it to an array)
1
vote
2answers
43 views
Find the minimum N such that the sum of beauty of all numbers from 1 to N is at least X
The beauty of a number is defined as follows :-
...
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[...
3
votes
2answers
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 ...
2
votes
1answer
41 views
Find four sets where each element from those four appears in at least two of those four sets
I have a list of sorted arrays ("sets") of integers $A_1..A_n$ where each element is unique w.r.t. the other elements in the same array:
$A_i = \{x_{i,1}..x_{i,c_i}\}$
$x_{i,p} < x_{i,p+1}$
$A_i$ ...
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 ...
3
votes
1answer
105 views
Find the smallest element greater than current element
my question is that given a list of integers (lets say A), for each element A[i], find the smallest element A[j] which could satisfy A[i] < A[j] and i < j. Return -1 if there is no such element.
...
0
votes
1answer
22 views
How to count stores in cache analysis of matrix multiplication
I'm trying to understand cache misses/iter and came across this that I couldn't understand or reason out.
For ijk iteration, my slides say that there are 2 loads and 0 stores.
...
2
votes
1answer
90 views
How to find efficiently the minimum modification to avoid close consecutive numbers?
I have an array of sorted numbers:
arr = [-0.1, 0.0, 0.5, 0.8, 1.2]
I want the difference (dist below) between consecutive ...
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:
...
0
votes
1answer
59 views
How to compare an element with other elements within an array efficiently for a condition
I need to compare each index with one another and associated array value as well.
For example,
...
