Questions tagged [arrays]

A sequential random-access data structure whose size can typically not be changed after creation.

Filter by
Sorted by
Tagged with
2 votes
2 answers
511 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$ ...
user avatar
  • 145
0 votes
2 answers
85 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 ...
user avatar
  • 35
0 votes
2 answers
182 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 =...
user avatar
  • 35
0 votes
0 answers
8 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 ...
user avatar
2 votes
1 answer
61 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 ...
user avatar
  • 45
2 votes
0 answers
46 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. ...
user avatar
0 votes
1 answer
105 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 ...
user avatar
  • 9
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 ...
user avatar
0 votes
0 answers
37 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 ...
user avatar
  • 37
0 votes
1 answer
17 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 ...
user avatar
1 vote
1 answer
106 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 ...
user avatar
  • 31
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{...
user avatar
2 votes
1 answer
21 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 ...
user avatar
  • 255
2 votes
1 answer
101 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 ...
user avatar
  • 121
0 votes
2 answers
82 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 ...
user avatar
-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?
user avatar
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 ...
user avatar
  • 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 ...
user avatar
  • 101
2 votes
1 answer
24 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 ...
user avatar
  • 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 ...
user avatar
1 vote
1 answer
45 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'...
user avatar
0 votes
1 answer
72 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 ...
user avatar
  • 101
2 votes
1 answer
39 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 ...
user avatar
1 vote
0 answers
23 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). ...
user avatar
  • 330
3 votes
1 answer
183 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 ...
user avatar
  • 67
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 ...
user avatar
1 vote
0 answers
22 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 ...
user avatar
2 votes
2 answers
104 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 ...
user avatar
2 votes
0 answers
27 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 ...
user avatar
  • 151
0 votes
1 answer
36 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) ...
user avatar
  • 171
0 votes
0 answers
21 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 ...
user avatar
  • 171
0 votes
0 answers
15 views

change an algo to obtain optimal run time

I have an algorithm that does the reverse of partition ...
user avatar
  • 35
1 vote
1 answer
57 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: ...
user avatar
  • 25
1 vote
0 answers
43 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 ...
user avatar
  • 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,...
user avatar
  • 25
1 vote
1 answer
114 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 ...
user avatar
0 votes
1 answer
117 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: ...
user avatar
0 votes
1 answer
93 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: ...
user avatar
  • 459
0 votes
0 answers
37 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 (...
user avatar
  • 101
0 votes
1 answer
141 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 ...
user avatar
2 votes
1 answer
70 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 ...
user avatar
-1 votes
1 answer
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 = \{ ...
user avatar
  • 201
1 vote
1 answer
88 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 ...
user avatar
  • 111
1 vote
0 answers
788 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,...
user avatar
  • 31
0 votes
0 answers
426 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 ...
user avatar
  • 159
0 votes
0 answers
5k 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 ...
user avatar
  • 101
1 vote
1 answer
71 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 ...
user avatar
  • 113
3 votes
1 answer
124 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 ...
user avatar
  • 131
1 vote
4 answers
2k 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 ...
user avatar
  • 251
1 vote
1 answer
117 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. ...
user avatar

1
2 3 4 5
11