Questions tagged [arrays]
A sequential random-access data structure whose size can typically not be changed after creation.
465
questions
1
vote
1answer
21 views
Sort a $d$-sorted array
An array is $d$-sorted if every key in the array is located at a distance at most $d$ from its location in the sorted array.
I need to write an algorithm that get a $d$-sorted array of length $n$ and ...
-3
votes
0answers
15 views
Reordering an array to maximize expression
You are given 2 arrays $a$ and $b$ of size $n$.
Your task is to reorder array $b$ such that the following expression is maximized.
$$(a_1\ ⊕\ b_1) \& (a_2\ ⊕\ b_2)\& (a_3\ ⊕\ b_3)\& \ ... \...
1
vote
1answer
27 views
Arrays and pointers
so I know the name of the array is a pointer to the first element of the array. But I've noticed something weird Here's the code.
Here is the result:
How is it possible that the pointer is pointing ...
1
vote
1answer
36 views
Quickly determine if insertion sort or quick sort is better
I'm in a scenario where ~30% of the time, my array is almost completely sorted, and the other 70% of the time, it is basically completely random. I want to quickly determine if my list is almost ...
0
votes
0answers
33 views
Why is LRU cache not implemented using doubly linked list with just two nodes? Do we even need double linked list?
I don't understand why do we need to have more than two nodes in doubly linked list when all we need to maintain is the most recent and least recently accessed nodes.
I was going through solutions for ...
0
votes
0answers
35 views
Array algorithm to fill an array in equal but alternate binary choices as close as possible given an already fixed configuration
Stuck on a problem with my roommate and can't seem to find any parallels to this.
The problem is simple to understand: you have two possible binary options: T or F.
You are given an array which ...
1
vote
1answer
27 views
Index variable takes up log(n) space?
In the definition of in-place algorithm, from Wiki, " However, this form is very limited as simply having an index to a length n array requires O(log n) bits."
How does an array index ...
0
votes
0answers
19 views
Reordering similar elements together within an array
I have a requirement where I need to group similar elements together within an original list.
For example:
I/P array:
...
0
votes
0answers
25 views
Implement Immediate Smaller Element problem using Stack
Immediate Smaller Element Problem:
Given an integer array arr of size $n$. For each element in the array, check whether the right adjacent element (on the next ...
0
votes
2answers
76 views
Given a sorted array with n integers, how to find the element that has no duplicates?
I am given a sorted array with n integers. All of the elements repeat exactly twice, while there is one element without duplicate. I need to solve it as efficient as it is possible by divide-and-...
1
vote
0answers
34 views
Dynamic array with 4x growth factor: Potential Method
I am curious on the use of the potential method for amortized analysis for a dynamic array which quadruples in size after it becomes full.
I understand how the potential function is defined and used ...
1
vote
1answer
72 views
Is there a name for an “array with no holes”?
How would you call an array [1, 2, 3, 4, 5, ...] that has (and ensures) the property of not having any undefined values through all its length.
"Dense" could work but it's not exactly what I ...
0
votes
1answer
36 views
Algorithm chalenge: find minimum range to cover all houses with light
N houses are located on a straight street which has K streetlights. Each streetlight has range R. Given N and K how to find minimum value for R?
N is an array containing location of each house.
K is ...
4
votes
2answers
162 views
Is there another type of list than arraylist and linked-list?
My question is not about how arraylists or linked-lists work, but why there aren't other types of lists.
From my understanding, memory is accessed linearly by adresses. Thus, you have the choice to ...
0
votes
0answers
25 views
Subarray containing all integers from 1 to $m$
I have faced the following problem in an entrance examination, and need to verify a few results plus a question part that did not manage to get in time.
Given an array $A$ of length $n$ which contains ...
0
votes
1answer
46 views
Recursive array
The following is a function to write a recursive function that accepts an array and a callback. Function returns true if a single value in array returns true when passed to the callback otherwise it ...
1
vote
1answer
55 views
Minimum number of swaps to make two arrays strictly increasing
I'm trying to understand the solution of the following problem (LC 801):
Given two arrays, A and B, of the same nonzero length, find the minimum number of swaps (A[i] <--> B[i]) to make A and B ...
0
votes
2answers
61 views
Randomize List with guaranteed Index Change
I usually post on Stackoverflow, but I got stuck with a problem which I think fits better here and I hope someone can help me. The task ist pretty simple:
Shuffle/Randomize an array/list
conditions:
...
0
votes
1answer
39 views
LinkedList: Remove the kth node form the end
Question: Write a function that takes in the head of a Singly Linked List and an integer k and removes the kth node from the end of the list. The removal should be ...
1
vote
1answer
49 views
Using hashing to solve 4-sum problem
The famous 4-sum problem is to find 4 elements at unique indices in an array which sum to a given X. I was looking at one solution I found:
...
0
votes
0answers
36 views
0/1 Knapsack problem. How does the total weight does not exceed the limit?
I am trying to wrap my head around the knapsack problem algorithm. I understood the most of it except one tiny thing.
On the left is the [val,weight] and on the ...
0
votes
1answer
103 views
design a strange data structure, is it possible?
I need a FIFO QUEUE that can do Insert and Remove from Queue in amortized $O(1)$ but extract min in $O(log n)$. is it possible?
When just find min is important (not removing) there is lots of $O(1)$ ...
0
votes
0answers
53 views
Competitive programming: Good Subsets problem
An array of length K is called good if for each subarray of the array, the sum of the subarray is not divisible by K+1. You are given an array A of length N. Find the number of subsequences of length ...
0
votes
0answers
20 views
Find the intersection point between two sorted arrays with unknown lengths in lesser than O(n)
Two sorted arrays of positive integers, X[] and Y[] are given.But, the array sizes are unknown to us. We may assume that accessing any index beyond the last element of the array returns -1. The ...
0
votes
1answer
83 views
0
votes
0answers
24 views
Counting elements in an array greater than a value and after the value
I have an array composed of integers from 1 through n. For each integer, I want to count the integers which are greater than that integer and occur after the integer's placement in the array in O(n*...
0
votes
0answers
14 views
Recursive Selection of Pivot from an Array
Suppose we have an array of integers $A$ of length $n$, which is assumed to be multiple of 5 for convenience in the discussion below. Now we try to pick a pivot $x$ from $A$ such that $x$ can divide $...
1
vote
2answers
45 views
A silly doubt on Computer Science Objects: Arrays, Lists, Strings, and Vectors, are they the same concept?
First of all I'm a Physics Student and I've been arguing with my brother concerning the usage and the fundamental meaning of a vector on Computer Science (CS).
I) Vectors
A vector have a axiomatic ...
2
votes
2answers
56 views
Finding the most frequent element assuming $\Theta(n)$ frequency
We know [Ben-Or 1983] that deciding whether all elements in an array are distinct requires $\Theta(n \log(n))$ time; and this problem reduces to finding the most frequent element, so it takes $\Theta(...
1
vote
1answer
74 views
Count minimum number of steps to destroy all blocks
Given a sequence of integers $A_x$ of length $n$ such that $1 \leq A_x \leq N$,in one step we can remove an element, but when we remove an element we also delete all adjacent numbers which have the ...
-3
votes
1answer
57 views
Subset sum problem with a complication
I have a sorted list of numbers. I know they can be divided into two parts. I also know the sum of those 2 parts. I want to know what these subsets are. How can i find them?
The size of my list can be ...
-1
votes
1answer
36 views
Finding which value I will be on after a certain number of steps
I have a fixed array: [a,b,c], I wanna loop through this 3-items-sized array for 7 times in order to find what I would get at that exact step.
The "value stack&...
2
votes
0answers
53 views
How to parallelize a summation efficiently
Say I have an array a[1..n], and I want to output an array s[1..n] with s[i] = a[1]+...+a[i]. What is the best (or at least standard) way to do so in parallel?
The way I can think of doing it, given m ...
2
votes
2answers
463 views
Find the length of the longest subarray having sum greater than k
I tried to solve this problem but could not do it better than $O(n^2)$.
My Algorithm:
...
1
vote
0answers
18 views
N-dimensional generalization of map and reduce?
Is there any conceptual generalization of higher-order functions like map and reduce but for N-dimensional objects (e.g. arrays or tensors)?
For mapping, I guess it would be a point-wise ...
-1
votes
1answer
73 views
What is Simple Uniform Hashing, and why searching a hashtable has complexity Θ(n) in the worst case
Can anyone explain nicely what Simple Uniform Hashing is, and why searching a hashtable has complexity Θ(n) in the worst case if we don’t have uniform hashing (where n is the number of elements in the ...
1
vote
0answers
45 views
Algorithm for summation with lowest maximum temporary sum
I've got this problem on my last exam, which I struggle to deal with.
Let's say we have array of $N$ integers (it can be float too, but let's say integers for sake of simplicity. We need to sum those ...
0
votes
0answers
55 views
Why do we need MinHeap for Meeting Rooms 2 Leetcode problem
I came across this problem online which is a Leetcode premium problem. Most of the people are solving this using Minheap. To me using minHeap for this seems like repetitive way to solve a problem if ...
0
votes
0answers
47 views
Reconstructing an Array via Time-Intensive Subset Queries
I am trying to design an algorithm for a problem, and the following is an auxiliary problem for which a good solution would imply a faster algorithm for the original problem.
I am given access to an ...
-2
votes
1answer
1k views
How to calculate the minimum price required to buy all the stones?
I have shared the question above. My current algorithm does the calculation in O((n^4)*(2^n)).
Can someone please help me out to solve this faster?
2
votes
1answer
77 views
$\Phi_1=1$ or $\Phi_1=2$ for the dynamic $\text{Table-Insert}$ , where $\Phi_i$ is the potential function after $i$ th operation, as per CLRS
The following comes from section Dynamic Tables, Introduction to Algorithms by Cormen. et. al.
In the following pseudocode, we assume that $T$ is an object representing the table. The field $table[T]$...
0
votes
0answers
40 views
Which advanced data structure to use?
For range queries on a subarray [L,R] , I want to find all the indices of successive maximums from left to right within O(log(R-L+1)), excluding index "L". I know using segment trees I can ...
1
vote
1answer
92 views
How to find the size of gaps between entries in an array so that the first and last element of the array is filled and the gaps are all of equal size?
I have an array a of n entries. I need to place a token on the first and last position of that array, so a[0] = 1 and a[n-1] = 1....
2
votes
1answer
81 views
Returning random integer from interval based on last result and a seed
Suppose we have an interval of integers [a, b]. I would like to have a function that returns random members from within the interval, without repetitions. Once that all members within the interval are ...
2
votes
1answer
42 views
How do you find all integers in a sorted array of size n that appear n/k times?
I try to find the solution to this problem:
How do you find all integers in a sorted array of size n that appear n/k times in less than O(klogn) time?
I could only find this question, where O(klogn) ...
1
vote
1answer
50 views
Smallest subarray problem
Say you have an array of integers like [1, 2, 3, 4, 5, 6], the problem is to find the smallest way to break up the array into sub-arrays where each sub-array satisfies the following requirement:
sub-...
1
vote
1answer
38 views
Find position in array where element-wise multiplication with string of 1 and 0s results in max value
I have a sequence of 1s and 0s. For example: $bits = [1, 0, 1, 1, 1, 0]$. I also have an array of positive integers. For example $arr = [12, 23, 4, 6, 8, 0, 24, 72]$. I need to find the index, $i$, in ...
0
votes
0answers
19 views
How to pick a random index in an array based on the index's value?
While solving a problem on leetcode, I used a heap to give the largest probable value. The problem statement is as follows:
Given an array w of positive integers, where w[i] describes the weight of ...
3
votes
0answers
48 views
Minimizing the sum of differences in a pair [duplicate]
You have two arrays, a and b
Both contain n elements, all positive and distinct.
you have to create a pair, by taking one number from each array, such that the sum of the differences of the pairs ...
1
vote
2answers
68 views
Amortized time for dynamic array
I'm struggling to understand one part from the book "Cracking the coding interview".
The author states inserting an element in a dynamic array is $O(1)$ most of the time, except when the array is full ...
