Questions tagged [arrays]
A sequential random-access data structure whose size can typically not be changed after creation.
527
questions
23
votes
3
answers
3k
views
Array access is O(1) implies a fixed index size, which implies O(1) array traversal?
Arrays are generally presented as data structures with $\Theta(N)$ traversal and $\Theta(1)$ random element access. However, this seems inconsistent:
if array access is really $\Theta(1)$, this means ...
- 34k
-2
votes
2
answers
83
views
Minimum absolute sum of 2 elements from 2 different lists
I am currently stuck on this problem, it is from a very highly competitive contest and so it is highly difficult as well. Below is the statement:
...
- 25.2k
0
votes
2
answers
57
views
Why do the pointers in Two-pointer algorithm move only towards each other?
Problem statement- Given a sorted array, print out the pair of elements of the array that have a sum of K, where K is a whole number.
The solution to the above problem goes like this:
With using the ...
- 3,912
0
votes
2
answers
99
views
0
votes
2
answers
54
views
Finding an element within an array that satisfies some rule
I saw a question on an old exam in my university course of DSA and I am not sure if the question is far too easy or if I am missing something.
The question is :
Given an array A that consists of N ...
1
vote
0
answers
60
views
Minimum swaps to rearrange array so that the same numbers are in consecutive positions
Problem: Given an array of $N$ integers in range $[1,M]$, count the minimum number of swaps to rearrange array such that the same values are in a row.
For example, given an array $[1,2,1,1,2,1,2]$.
...
- 34k
0
votes
1
answer
176
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 ...
CommunityBot
- 1
0
votes
1
answer
47
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 ...
CommunityBot
- 1
1
vote
1
answer
155
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 ...
CommunityBot
- 1
0
votes
1
answer
84
views
Finding sequences of 0's in a 2D binary grid
Requirements:
Given a 2D array of 1's and 0's (black and white cells) find blocks of white cells of size 1xT or Tx1 where T >= 1. Any block should not be a subset of a larger block.
Return the ...
CommunityBot
- 1
0
votes
1
answer
68
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 ...
CommunityBot
- 1
2
votes
2
answers
164
views
Given n positive integers, pick two elements and subtract each by one with one operation. Find maximum number of operations
Problem Description: We have an array of $n$ positive integers and in one operation we have to choose two elements in the array and decrease them by $1$. (Elements on which we are performing this ...
- 231
-1
votes
1
answer
124
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 ...
CommunityBot
- 1
0
votes
2
answers
662
views
Maximum difference between maximum and minimum frequency in a subarray
Can anyone please help me with a better solution than O(n^3) for this problem?
So the problem is given a string, we want to output the substring's length where freqency[c1] - frequency[c2] is MAX.
c1 =...
-1
votes
1
answer
47
views
0
votes
2
answers
116
views
Maximum subarray sum of given length range
Can anyone please help me solve this better than $O(|a-b| \cdot n)$?
Given an array of both negative and positive numbers, we want to find the maximum sum of the elements in contiguous subarray having ...
- 34k
0
votes
1
answer
71
views
How do i delete one single unequal element from an array of equal elements without using hashing?
The rules of the question state that:
Only one element is different.
Rest are all same.
Array A size is 8.
I need to find the different element and remove it (Hashing cannot be used).
I have not ...
CommunityBot
- 1
2
votes
2
answers
522
views
How can I apply binary search to find two adjacent increasing elements in an unsorted array?
I need to write a function that gets an array of numbers $a$ as an input and returns an index $i$ such that $a[i]<a[i+1]$ if it exists, if such $i$ doesn't exist return $-1$. (return any index $i$ ...
- 3,912
0
votes
0
answers
9
views
Strides of array and their relation to temporal and spacial locality
I'm really having trouble understanding strides of arrays, and how they relate to temporal and spatial locality in general. I was hoping I could get some help understanding it here.
I have the ...
2
votes
1
answer
65
views
Find two very frequent items in a given array of comparable items
I am new to this community and I have a question regarding a problem I was trying to solve. Could anyone review my algorithm for solving this problem?
I want to emphasize also that the algorithm must ...
- 34k
2
votes
2
answers
153
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 ...
CommunityBot
- 1
1
vote
1
answer
143
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....
CommunityBot
- 1
2
votes
1
answer
2k
views
To find median of $k$ sorted arrays of $n$ elements each in less than $O(nk\log k)$
How do I efficiently find the median of $k$ sorted arrays each of length $n$? Note that the total number of elements will be $nk$. I know it can be done in $O(nk \log k)$ time using merge technique. ...
- 270k
2
votes
1
answer
151
views
Array vs Linked List Implementation of Stacks (in JS)
Let's say I want to make a Stack class in JavaScript. The class will have a push() and a pop() method. I have two options for ...
- 345
1
vote
1
answer
90
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
...
CommunityBot
- 1
2
votes
0
answers
50
views
Find minimum difference between pairs of numbers chosen from array of ranges
I recently thought of this problem, and I think it's very interesting. We are given an array of $N$ numbers, but we don't know the numbers themselves, only a possible integer range for each number. ...
- 338
3
votes
1
answer
116
views
Improve algorithmic complexity
We have an array of N size. We have to perform Q queries on it, in which each Query contains and Index I for which we do:
...
CommunityBot
- 1
0
votes
1
answer
126
views
$ \Omega(m)$ and $O(m)$ meaning in theorem proof about dynamic array complexity
My algorithms and data structures' book states that to create a dynamic array the following procedure is followed:
Let $d$ be the length of an array $ a $ and $n $ the number of elements stored in ...
CommunityBot
- 1
1
vote
1
answer
127
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 ...
CommunityBot
- 1
0
votes
1
answer
107
views
what could be more efficient way for this problem?
So I'm trying to solve this problem and I came up with a brute force solution. I was wondering how can i make it more efficient ?
Problem:
Suppose i have resources and integer that denotes at what ...
- 161
0
votes
0
answers
38
views
algorithm for finding order of index variation in multidimensional array data
Given a set of tuples, I want to determine if the set covers the whole space of possible values, and in which order the indices vary.
This is best explained with 2-dimensional examples:
In the ...
- 101
0
votes
1
answer
246
views
0
votes
0
answers
43
views
find element in array that has the highest number of divisors from within the array
Given array of positive integers find the element with the maximum number of divisors from the array excluding 1.
The array may contain duplicates. Below is a sample solution, however I am curious if ...
- 37
1
vote
1
answer
121
views
Reasoning behind specifically doubling the array size upon reallocation
I am trying to understand the actual reasoning behind creating a new dynamic array of double the size of the original array once it gets full as opposed to any reasonably random number (not too small ...
- 345
0
votes
1
answer
18
views
Termination condition for max of array using divide and conuqer approach
I want termination proof of divide and conquer approach to find max of array,I want equational proof in form of lemma.Below is my attempt.I have got accepted everything in dafny ,it is only pointing ...
- 59
10
votes
2
answers
39k
views
What is a contiguous subarray?
What is a contiguous subarray? I have tried searching online and have found pages about solving the largest contiguous subarray problem but none with a definition or explanation of what contiguous in ...
- 99
6
votes
1
answer
188
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 ...
CommunityBot
- 1
1
vote
1
answer
17
views
Find indices of equal cells in a matrix
I am trying to find the indices of all the equal elements in a matrix $\left ( n\times m \right )$. For each pair of matching cell, I will perform a specific function on them. For example:
$ \begin{...
- 270k
2
votes
1
answer
23
views
How to create tensors at runtime?
I have a small personal CAS project around linear algebra which involves, among other things, manipulating tensors. When I talk about tensors, I mean them according to the physical / mathematical ...
- 270k
0
votes
2
answers
98
views
Does creating a deep copy of a string of size N (in python) take space complexity O(N) or O(1)?
My question comes from solving this LeetCode question, in which we are given a string of characters with size N, and one of the solutions is to use a hashmap (dictionary in Python) to count the ...
- 3,912
-2
votes
3
answers
86
views
Is O(k*n) in this case linear?
Problem: find sum of k element in array and it is biggest?
time complexity of my algorithm is O(k*n).Is it linear complexity?
1
vote
1
answer
129
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.
...
- 3,976
0
votes
0
answers
36
views
Algorithm to create N bands with dynamic range
I'm a little stuck with a problem creating an array of data that contains N bands with a dynamic range given a total revenue and N stores, and my maths has not been tested in this manner for quite ...
- 101
0
votes
0
answers
26
views
How to find 2 close elements in a array in O(n)? [duplicate]
Let a1,...,an be a sequence of real numbers, n > 1. Let m be the minimum of the sequence, and let ...
- 34k
2
votes
1
answer
26
views
How to translate a virtual Bitvector B to an integer array W | 32-bit integer array
Can somebody please explain to me, how one can calculate W = 2762827861, 1991065600 from previous representation B? An example calculation would be great.
I am unable to figure out how the translation ...
- 156
1
vote
4
answers
3k
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 ...
0
votes
0
answers
34
views
Are arrays “more abstract” than stacks or queues?
It seems to me that an array can be used as a stack or a queue and for various other things.
In my mind this makes an array a higher order abstraction compared to those other two.
Is this an ...
- 111
1
vote
1
answer
55
views
Why Prefer Two Stacks to an Array for Undo/Redo?
It seems to be a popular opinion that "the right way" to implement undo/redo is "using a stack." (particularly in the context of an algorithms and data structures interview.)
Here'...
- 1,399
0
votes
1
answer
114
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 ...
CommunityBot
- 1
2
votes
1
answer
51
views
Is there a way to represent multi-dimensional arrays in lambda calculus?
I am currently studying lambda calculus, and would like to represent an array that accepts multiple dimensions. I still haven't figured out how to implement uni-dimensional arrays though.
I have found ...
- 5,164