Questions tagged [arrays]

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

Filter by
Sorted by
Tagged with
1
vote
1answer
30 views

Generate all combinations of a set/array with specific conditions

Apologies if this isn't posted in the right stack exchange, but I'm trying to come up with an algorithm that generates a set of sets ('set' as synonymous with 'array') with the following conditions: ...
0
votes
2answers
43 views

Can you insert into sorted list with time O(1)?

Wondering if this was possible. If I have a sorted list, can I find the right spot for an integer and insert it, all in O(1) time? The only way I can think to do this is via having a MASSIVE hashmap ...
3
votes
1answer
46 views

Why is memory one dimensional?

Addresses in system programming languages like C are one dimensional (i.e. one number). This forces the programmer to make a decision whether matrices are stored "row major" or "column major" causing ...
0
votes
0answers
16 views

What are some unusual or creative implementations of ADTs you've seen?

While learning about ADTs in a data structures course, we learned that the List ADT is most commonly implemented using linked nodes or arrays. Are there any other fundamentally different and unusual ...
0
votes
1answer
41 views

How to shift a matrix by x rows and y columns in the most efficient way?

My objective is to shift rows by x and columns by y in a 2d matrix. My problem is to solve this objective in an efficient manner. x and y could be negative or positive. Negative would mean up/left ...
1
vote
0answers
10 views

Minimising total access time to elements in an array which is accessed sequentially

Starting with two examples: for(i = 1; i<10; i++) {B[i] = 0;} for(i = 1; i<10; i++) {B[2i] = 0;} In the first example, ...
1
vote
1answer
26 views

Is it possible to find a supersequence of a single array?

In Jeff Erickson's Algorithms textbook, the chapter on Dynamic Programming asks you to "Describe an efficient algorithm to compute the length of the shortest oscillating supersequence of an arbitrary ...
2
votes
1answer
37 views

Finding largest sum of $k$ elements below threshold

I was working on a project and am stuck in the middle unable to find an optimal method to solve this problem. Consider an array $A$ of $n$ elements. I have to choose $k$ elements such that the sum of ...
0
votes
0answers
23 views

Reverse of In-place algorithm for interleaving an array

How to do the reverse process of In-place algorithm for interleaving an array question?
1
vote
1answer
60 views

Array segmenting algorithm

I have a sorted array of integers [x, ..., n, ..., y] so that x > 0 n - x = random positive integer The array might look something like this: [1, 2, 3, 15, 16, 17, 120, 121, 122, 123, 124, 125, 126,...
0
votes
1answer
42 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 ...
2
votes
1answer
29 views

Minimum moves to “stabilize” an array

We have given an array of size $N$, consisting of positive integers, and an integer $H$. We also know that an array is stable iff $|A_i - A_{i-1}| \leq H$ for each $1<i<N-1$. We can modify the ...
1
vote
1answer
39 views

What algorithms for unification over (multidimensional) array terms?

I am looking for references on implementing unification over multidimensional array terms. Are there specialized unification algorithms for those cases? I wasn't able to find satisfactory literature ...
0
votes
1answer
33 views

pseudocode to split number value to array of numbers

How to write a pseudocode to split a number value to array of numbers? Let's say the number value is 12345. I need to convert it into [1,2,3,4,5].
-1
votes
1answer
77 views

Time complexity of removing duplicates in lists

Question I am wondering what is the minimum time complexity of get the unique value of a array in two conditions: keep the order or not. For example, suppose we have a original array ...
5
votes
2answers
642 views

How can merging two sorted arrays of N items require at least 2N - 1 comparisons in every case?

The HW question, on page 362 of Data Structures and Algorithms in C++: Fourth Editionby Mark Allen Weiss, reads as follows: Prove that merging two sorted arrays of N items requires at least 2 * N - ...
-1
votes
1answer
569 views

Minimum number of cans needed to carry all used water

so I've just attempted an online technical test. It was on hacker rank however I'm sure leetcode usually has the same (and more) so thought i'd ask. I could not think of a nice solution and cannot ...
1
vote
0answers
47 views

finding the parent index in an interval heap (stored on an array) given a child index

an interval heap is a binary tree stored on an array where the size of each node is 2. i would like to be able to find the index of a parent and find one of the child indices given the index of a ...
1
vote
1answer
72 views

Find number of triples that sum up to zero in query-intervals

My problem is that we have an array of $N$ integers $(N <=5000)$ on the interval $[-10^6,10^6]$. We also have $Q$ queries $(Q <= 10^5)$ giving us some range in the array. For each query, we ...
0
votes
0answers
52 views

Selection Sort vs Merge Sort

I recently wrote a written test for the recruitment of Scientists/Engineers in ISRO(Indian Space Research Organization) few days back and the following question appeared in the test. Of the following ...
0
votes
0answers
25 views

Maximising sum of associated elements

I have a set of elements. Each element is connected with every other element by a path of length $l_i,_j\geq0$ (where i$\neq$j). I have to calculate the maximum sum of path length such that I should ...
1
vote
2answers
276 views

Sorting a large list of test scores

You have a large list (say N > 10000) of test scores which you would like to sort. The test scores are between 1 and 100. What is quickest way to sort the list? First thought. We have a O(N log N) ...
1
vote
0answers
13 views

When was the dynamic array first introduced as an example for amortized analysis?

I'm writing a report on amortized analysis, and I'm using the example of a dynamic array to explain each method. I think it would be nice to add a reference to when this example was first used, as it ...
0
votes
1answer
111 views

Which sort algorithm to choose given two specific arrays?

Interview question: Given array A which contains only odd numbers and array B which contains only even numbers, explain which sort algorithm would you choose. I said merge sort. I thought that ...
1
vote
1answer
154 views

Selecting elements from two arrays to get a target sum

Let $A$ and $B$ be two arrays of size $n$ with positive integer values. Let $k$ be a given positive integer. Design an algorithm to solve the following problem. For each index $i$ ($1\leq i \leq n$)...
4
votes
1answer
95 views

Sort array of duplicate integers in place

Given an array of integers within [1, n] where n = size of array, some elements may appear more than once. Could we sort it with just 1 extra space and in O(n) time?
2
votes
0answers
38 views

Find a non-minimal sequence of elements covering the support set

Consider a sequence $s$ of $n$ integers (let's ignore the specifics of their representation and just suppose we can read, write and compare them in $O(1)$ time with arbitrary positions). Denote $\text{...
0
votes
1answer
103 views

Given an array arr[] of N integers. Do the following operation n-1 times

For every Kth operation: Right rotate the array clockwise by 1. Delete the (n-k+1)th last element. eg: A = {1, 2, 3, 4, 5, 6}. Rotate the array clockwise i.e. after rotation the array A = {6, 1, 2, ...
2
votes
1answer
53 views

Space-efficent storage of a trie as array of integers

I'm trying to efficiently store a list of strings in an array with the following constraints: All strings consist of 8-bit characters (0..255). The final trie is static, i.e. once it is built, no ...
0
votes
0answers
37 views

What constitutes a minimal-sum section of an integer array

I'm having trouble understanding what constitutes a "minimal sum section" of an integer array. My book defines it as the following: Let $a[0],\dots, a[n-1]$ be the integer values of an array $a$. ...
3
votes
1answer
49 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: ...
6
votes
3answers
367 views

Recover an array from its insertion indices

An array is built starting with an empty array, and then a sequence of insertions: insert $a_1$ at index $z_1=1$ insert $a_2$ at index $z_2$ insert $a_3$ at index $z_3$ ... and so on. When we ...
1
vote
0answers
23 views

Intersection of 2 arrays

Here is a question i came across : Given two arrays, write a function to compute their intersection.Here we will allow the duplicates. Note: Each element in the result should appear as many ...
3
votes
1answer
47 views

Are all data structures in the von Neumann architecture based on the array, or array-like?

I am an old Pythonista now learning C and how various data structures and types are implemented, such as binary trees and hash tables. Learning about the latter, leads me understand that the hash ...
1
vote
2answers
78 views

Efficient algorithm for finding optimal sum from both arrays

I have two arrays(A,B) and a sum M. I need to find one number from each array that makes the sum M. If there is no two elements that form sum M, then nearest and less than M sum is the solution. See ...
2
votes
3answers
255 views

Remove x last elements of an array and reinsert them before position y

I am looking for an algorithm to move a subarray in before an element (which is not part of that subarray) in the same array where the last element of the subarray is the last element of the array ...
1
vote
1answer
81 views

Return the subset with smallest cardinality of an array whose elements sum to at least a given value

Suppose we are given an array $A[1\ldots n]$ and a value $C$. Is there an algorithm with linear expected runtime that can produce an array that is the subset with smallest cardinality of $A[1\ldots ...
3
votes
1answer
53 views

How to answer multiple queries efficiently?

I am given a $N$-length integer array. For each integer, I am given 4 values: $$[\mathit{left},\mathit{right},t,\mathit{value}]$$ $$1\leq \mathit{left},\mathit{right},t\leq N$$ For each query, I ...
2
votes
2answers
274 views

Maximum number of multiples of an array element preceding it

Given an array of size $n$, we have to find the maximum number of multiples of $A[i]$ in the array, where the indexes of the multiples should be less than $i$. For example, given the array 36 40 ...
3
votes
2answers
75 views

How to sort a large list of elements where everything is sorted but k elements?

Assuming the list is very large, and $k$ is very small, what's the fastest algorithm to sort this list?
1
vote
2answers
48 views

Algorithm Design: Efficient O(n) algorithm to get the ith to jth largest elements in an array

I am trying to design an efficient algorithm that retrieves the ith to jth largest elements in an array. For example, if the following array is the input: ...
2
votes
0answers
45 views

Integer-array indexing (e.g. numpy.take) as function composition: where can I find more resources?

For context, one of Numpy's features is that an an array of integers can be passed as an index to an array, and this selects values at all of the specified positions, in any order with possible ...
0
votes
0answers
43 views

Is there an algorithm to compress a string array represented as pointers to a long string to pointers with a compressed version of the long string?

In a program I am writing, I represent an array of strings as a long string and have pointers point at the various substrings to present my array. E.g. ...
3
votes
1answer
70 views

Why is LinkedList useful?

If you implement a stack with a dynamic array-based with LinkedList you need more memory than with a dynamic array, and with dynamic array for insert in amortized cost is O(1), so the advantage of the ...
0
votes
0answers
26 views

Minimum amount of rectangles to create a 2-dimensional matrix

From this codegolf question. Consider an $r$ by $c$ matrix of nonnegative integers, called $M$. You also have a zero matrix of the same dimensions, called $N$. A "move" consists of replacing a ...
1
vote
3answers
563 views

Why is heap insert O(logN) instead O(n) when you use an array?

I am studying about the arrays vs heap for make a priority queue For check the heap implementation I am reviewing this code: Heap , but I have the following question. Heap is based on array, and ...
0
votes
0answers
54 views

Finding the rightmost element in an array of duplicate elements using binary search

i was reading Binary Search in the wikipedia and i came across this part of 'rightmost index of an element in an array of duplicate elements'. i understood the process of determining the leftmost ...
0
votes
1answer
53 views

Filler Algorithm

I am curious to know if there is an algorithm that, given an array of decimals and integers, and given an integer, returns a sequence in descending order, composed of those numbers of the input array ...
1
vote
1answer
54 views

Counting common values in two arrays

given two arrays of integers A and B of size m, with values in the range [-n,n]. I want an algorithm to count how many common values are in A and B , if a value is repeated we only count it once , ...
0
votes
1answer
95 views

Find pair with maximum Appeal value

Find pair with maximum Appeal value. Input: Array Output: index {i, j} ( i = j allowed) with maximum Appeal Appeal = A[i] +A[j] + abs(i-j) Example 1: Input: [1, 3, -1] Output: [1, 1] Explanation: ...

1
2 3 4 5
9