Questions tagged [arrays]
A sequential random-access data structure whose size can typically not be changed after creation.
495
questions
0
votes
1answer
21 views
Give an O(n^2) algorithm to solve
This is my homework question
Given an array A[1..n] of n integers, we want to decide if there exist i and j, where 1 ≤ i , j ≤ n, such that
A[i] + A[j] = α for a given value α.
Give an O(n^2) ...
0
votes
0answers
18 views
Why the last elements of the array of heap is itself heap
If we represent a heap using array the 2nd half of the array will be represent the leaf nodes of the heap. But I can not understand for array of length n, all elements in range A[[n/2+1]....n] are ...
0
votes
0answers
14 views
change an algo to obtain optimal run time
I have an algorithm that does the reverse of partition
...
1
vote
1answer
51 views
Merging sorted arrays stored as linked lists
I have $k$ sorted arrays stored as linked lists. I need an algorithm to merge them into one single sorted array, also stored as a linked list. How can I do that?
My Code:
...
0
votes
0answers
22 views
Finding a full collision within a large array
I apologize for the vagueness of the title, but this question is quite difficult for me to describe.
For that reason, I'm unable to directly convey my problem.
In an effort to circumvent this, I've ...
0
votes
1answer
39 views
prove sub array has a definite form with distinct end point integers
An array has elements from set {0, 1, 2}. A span SP of an array is any interval [start S, end E] such that the sub array must contain all elements from {0,1,2}.
For example: in Array A = (0,1,0,1,1,2,...
1
vote
1answer
42 views
House Robber DP Algorithm (Not three in a row)
This is a similar question to A variant of the house robber problem but instead of the general case, I'm wondering how you would solve the standard house robber problem, but when you cannot rob from ...
0
votes
1answer
89 views
What could be the most efficient algorithm to find index in an array that matches given conditions?
I have an array A with n elements. I am trying to write an efficient algorithm to find the index of elements that matches condition A[j-1]>=A[j]<=A[j+1].
Example:
...
0
votes
1answer
32 views
Array Doubling Size Strategies
I would like to discuss resizing strategies for arrays please. If you have an array of $k$ initial size and it gets full, so you would like to choose from one of the following approaches:
Approach 1: ...
0
votes
0answers
15 views
Longest subarray without duplicates within distance K
You are given an array $A$ of of integers, length $N$. What is the longest ("sub") array you can generate from $A$, such that there are no duplicates within distance $K$ of one another. The (...
0
votes
1answer
29 views
minimum insertions and deletions required to ensure that each value X occurs X times
I would like to brainstorm/get some advice/tips regarding the following question. Given an array,you can either insert elements or you can delete elements from it.Note the insertion/deletion must be ...
2
votes
1answer
47 views
array empty cell search algorithm
I'm Telecommunication student so I don't have Computer Science background, just in case if my question looks stupid.
Here is my scenario:
Consider an empty array named ...
-1
votes
1answer
32 views
how to optimise this
Say you are given a matrix $M (A \cdot B)$ when $A$ is the number of rows and $B$ is the number of columns. Now we are free to pick one element from each column. Lets say these elements are $E = \{ ...
1
vote
1answer
51 views
More efficient way to parse array into binary search tree
Let's assume I have array which I need to parse into binary tree
...
1
vote
0answers
241 views
Minimum no of swaps to be done in an array such that, no two adjacent elements are same
Given an array of size n, find minimum number of swaps required, so that no two adjacent elements are equal. For ex-
n = 6, a[] = {1, 1, 5, 2, 5, 5}, answer = 1, ( swap a[0] with a[4] or
a[5] )
n = 8,...
0
votes
0answers
228 views
Minimum Number of Refueling Stops with Dynamic Programming
This is a question from Leetcode and I wanted to solve it with Dynamic Programming. upon seeing the solution, I am not able to get the intuition behind the logic. I was able to understand the solution ...
0
votes
0answers
2k views
Find the magic value from an array of N numbers
I was asked this problem recently in an interview however, I failed to provide an optimal solution to it.
Given an array $A$ of $n$ numbers, the magic factor of $i^{th}$ element is
equal to the ...
1
vote
1answer
51 views
Map two arrays given a map of possible mappings
Given two integer arrays a and b and a map m which for each element ...
3
votes
1answer
61 views
Algorithm to Compute High Water Mark
I saw this algorithm question which is as below.
There is a server that receives request Ids that are positive integers.
The High Water Mark (HWM) for the server at any instant of time is defined as ...
1
vote
3answers
1k views
Minimum number of increment / decrement operations to make an array distinct?
I've been stuck on this problem for some time now..
Given an array A of size N that ranges between [1..N], a "move" is to increase or decrease an element (by 1). After each move the array ...
1
vote
1answer
70 views
Check array in linear time with a constant space complexity
Given an array of integers I have to return true if all the elements in the array are different or all the elements are the same. Otherwise, I have to return false.
E.g.
...
0
votes
1answer
38 views
How to prove that a binary heap can't be sorted with complexity that better than O(nlogn)
I am trying to prove that you can't sort binary heap with better complexity than O(nlogn).
We proved at class that every sort based on comparison can't have better cocmplexity than O(nlogn) and i ...
0
votes
1answer
111 views
In C++ how does "sizeof(array)/sizeof(array[0])" give the number of elements in an array? Why isn't it affected by the length of each element?
I'm playing around with C++ and was looking at how to loop through an array of unknown length. The following code was suggested and works perfectly from the little testing I've done:
...
2
votes
2answers
194 views
Sort an array with a constant number of unsorted elements
I am trying to sort an array that I know to have a constant number of unsorted elements (elements that are not in their right place).
In the solution I looked at they say you can do this in $O(n)$ ...
0
votes
1answer
32 views
Are single-dimentional arrays better than multi-dimentional in the GPU?
I'm making simulations like Ant colony simulation, boids, and cellular automata in Go (to learn Go), but I believe this can apply to most languages.
From what I've read (this), using 1D arrays is ...
0
votes
0answers
65 views
Multiplication of Upper triangular matrix and Lower triangular matrix
If I have an Upper triangular matrix A and Lower triangular matrix B, what could be the most efficient algorithm to get AxB and BxA.
Also what would be the formula for total number of multiplication ...
0
votes
1answer
31 views
mapping function to map the index of Lower triangular matrix
If I have a Lower triangular matrix of order n and I want to store non-null elements of this matrix in 1D array from first row to last row and within a row from left to right. What could be the ...
0
votes
1answer
58 views
What is the time complexity of a linear search performed using 2 pointers?
For an array, I'm using a left pointer (pointing to 0) and a right pointer (pointing to end).
For every iteration, if my search element is not found, I increment left and decrement right.
This ...
1
vote
1answer
39 views
Why does Insertion sort take linear time in this case?
Remove any 5 elements from a sorted array of n items and replace them with 5 new elements.
Why does running Insertion sort again on this array take linear O(n) time, I tried counting the number of ...
18
votes
3answers
3k views
Time complexity $O(m+n)$ Vs $O(n)$
Consider this algorithm iterating over $2$ arrays $(A$ and $B)$
size of $ A = n$
size of $ B = m$
Please note that $m \leq n$
The algorithm is as follows
...
0
votes
1answer
69 views
Find the minimum sum of distances between sets of points to a straight line in a plane
Given $n$ dots on a plane, such as: n couples ($x_i$,$y_i$)
I would like to find a line parallel to y-axis ( $x=b$ ), such that the sum of all of the point's distances from that line will be minimal
...
1
vote
1answer
26 views
2
votes
1answer
109 views
Searching in sorted array with $O(\log n)$
Recently been practicing some recent exams, there was a problem I could not comprehend the given answer, the question is as follows:
Suppose array $A[1..n]$ consist of $n$ distinct integers that is
...
1
vote
3answers
240 views
Intersection of two arrays
As part of a project i'm doing I have been looking for a way to find common values between 2 arrays including duplicates.
For example;
A = [2, 2, 3, 5]
B = [2, 2, 5]
would return the array;
Common ...
1
vote
1answer
115 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 ...
1
vote
1answer
30 views
Arrays and pointers [closed]
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
46 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
41 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
36 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
35 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
26 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
42 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
192 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
53 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
2answers
98 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
44 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
168 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
77 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
102 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 ...
