Questions tagged [arrays]
A sequential random-access data structure whose size can typically not be changed after creation.
535
questions
-1
votes
0
answers
23
views
0
votes
1
answer
26
views
Construct an objective function that favors the sorted permutation
I was looking into complexity theory and disappointed by the fact that a problem as simple as sorting an array isn't in the class $P$. This is because the class is defined only for decision problems (...
- 307
5
votes
2
answers
1k
views
Why does the order of the nested loops matter when solving the Coin Change problem?
The Coin Change problem is stated as:
Given an integer array coins[ ] of size N representing different
denominations of currency and an integer sum, find the number of ways
you can make sum by using ...
- 161
0
votes
1
answer
28
views
Is this an inversion problem?
I understand that total inversion in a sequence is the number of swaps that need to be done, to sort the sequence. And the best approach to solve this problem is to count swaps in a merge sort of the ...
2
votes
4
answers
84
views
Algorithm that finds 4 "O"s or 4 "X"s on a diagonal, horizontal, or vertical
My algorithm homework revolves around matching 4 "O"'s or 4 "X"'s on a diagonal, horizontal, or vertical. ...
- 123
-2
votes
1
answer
31
views
Inversion array of a given array
Let A[1...n] be an array of n distinct numbers. The ordering of the numbers is any permutation of [1,2,...,n]. An array Inv_A is defined as follows: Inv_A[i] = number of elements A[j] such that j<i ...
1
vote
1
answer
37
views
Are there adaptive algorithms/data structures for sparse and non sparse vectors?
A sparse 1D array of integers is commonly encoded as pairs of [index, value], which consumes 2 memory spots per value.
A dense 1D array is commonly encoded as a linear array of values [value1, value2, ...
- 131
1
vote
1
answer
49
views
Unable to understand how the while loop extracts the least number of coins with given sum
I was reading this classical Coin Problem (7.1): Given a set
of coin values coins = {c1, c2,..., ck} and a target sum of money n, our task is to
form the sum n using as few coins as possible.
I fully ...
- 13
0
votes
0
answers
24
views
Display XY data on computer
I would like to experiment with displaying the output of an analog to digital converter on computer. Samples of the ADC output would determine the intensity of one pixel.
The input to the ADC is an ...
25
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 ...
- 370
-1
votes
2
answers
108
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:
...
0
votes
2
answers
56
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 ...
- 65
1
vote
0
answers
71
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]$.
...
- 159
0
votes
2
answers
98
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 ...
- 1
2
votes
2
answers
540
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$ ...
- 164
0
votes
2
answers
875
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 ...
- 53
1
vote
2
answers
3k
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 =...
- 53
0
votes
0
answers
14
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 ...
- 65
2
votes
0
answers
58
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. ...
0
votes
1
answer
110
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 ...
- 9
0
votes
0
answers
39
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
0
answers
96
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
0
votes
1
answer
21
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 ...
user139614
1
vote
1
answer
211
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 ...
- 131
1
vote
1
answer
23
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{...
- 11
2
votes
1
answer
30
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 ...
- 255
2
votes
1
answer
303
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 ...
- 121
0
votes
2
answers
148
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 ...
- 113
-2
votes
3
answers
89
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?
- 11
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
29
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 ...
- 101
2
votes
1
answer
27
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 ...
- 123
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
72
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'...
- 111
0
votes
1
answer
99
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 ...
- 101
2
votes
1
answer
73
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 ...
- 145
1
vote
0
answers
27
views
N dimensional point, storage and access
Consider the case where you have 3-dimensional space. You want to know whether at a given point (x,y,z) in space, does anything exist(just like checking if in a 3D array at (x,y,z) is there a 1 or 0). ...
- 539
3
votes
1
answer
218
views
Algorithmic problem on sliding windows
Given a zero-indexed, unsorted array, $a$ of integers (can be positive, negative, or zero) of size $n$. A window of size $k~(k < n)$ is defined as a subarray $a[i...i+k]$ for every $0 \leq i \leq n ...
- 67
0
votes
1
answer
82
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 ...
2
votes
2
answers
265
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 ...
- 21
1
vote
0
answers
25
views
Thought Process for largest Container of Water Problem
There is a common leetcode problem that asks
Given $n$ non-negative integers $a_1, a_2, \dots, a_n$, where each represents a point at coordinate $(i, a_i)$. Then $n$ vertical lines are drawn such ...
2
votes
2
answers
166
views
Searching through an unsorted array with a better than O(n) complexity?
This question kind of puzzled me, it was presented as a homework assignment for 2nd year undergrads and one of them approached me in case I could give him some pointers, but the problem is I couldn't ...
Kao
2
votes
0
answers
28
views
Fast calculations using fast-Fourier convolution
Consider an array $X$ with shape $H \times W$. Let $Y$ be the other array of the same shape and $Z$ is an array of shape $h \times w$.
We want to construct an array $R$ of shape $(H-h + 1, W-w+ 1)$ by ...
- 151
0
votes
1
answer
45
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) ...
- 167
0
votes
0
answers
22
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 ...
- 167
0
votes
0
answers
16
views
change an algo to obtain optimal run time
I have an algorithm that does the reverse of partition
...
- 35
1
vote
1
answer
120
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:
...
- 25
1
vote
0
answers
44
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 ...
- 11
0
votes
1
answer
40
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,...
- 25