Menu
  • HOME
  • TAGS

Find the maximum value of minimum of each subarray of non fixed length x where 1<= x <= N

Tag: algorithm,dynamic-programming

Interview Question:

You are given N number in an array. A group of a numbers is a non-empty contiguous segment of array.The size of group is the number of numbers in that group.

"A" is the minimum number in that group.Task was to find each x such that 1 <= x <= N the maximum value of "A" among all group of size x.

For example if N = 3 and number are 1,2,3 ,then the answer will be 3,2,1

Numbers can be repeated in the array like N=7 and numbers are =1,2,3,4,5,4,6

For explication, the following C code is a naive solution:

#include <stdio.h>

int main() {
    int a[] = {6,1,3,2,5,4,7};
    size_t N = sizeof a / sizeof *a;

    for (size_t i=0; i<N; ++i) printf("%d ", a[i]); puts("\n");

    size_t group_size, start, i;
    int max, min;
    for (group_size = 1; group_size <= N; ++group_size) {
        max = 0;
        for (start = 0; start <= N - group_size; ++start) {
            min = a[start];
            for (i = start + 1; i < start + group_size; ++i) {
                if (a[i] < min)
                    min = a[i];
            }
            if (min > max)
                max = min;
        }
        printf("%d ", max);
    }

    return 0;
}

Output:

6 1 3 2 5 4 7

7 4 4 2 2 1 1

Best How To :

Very brief sketch of a linear-time solution: for each array element, compute the size of the maximal group for which that element is the minimum. (Break ties by treating the first of two equal elements as lesser.) Sort the elements by their associated size, in linear time using a degenerate bucket sort. Scan the elements by size large to small, outputting the maximum element seen so far (i.e., the maximum element whose group size meets the current threshold).

The tricky step is computing the group sizes. We keep a stack and scan the array beginning to end. For each element, we pop the stack elements greater than it, thereby ending their groups. Here's a trace on 6 1 3 2 5 4 7.

stack: (-inf @ -1)  {sentinel}

6 1 3 2 5 4 7 -inf  {sentinel}
^
stack: (-inf @ -1), (6 @ 0)

6 1 3 2 5 4 7 -inf
  ^
pop (6 @ 0): group size of 6 is (1 - (-1)) - 1 = 1
stack: (-inf @ -1), (1 @ 1)

6 1 3 2 5 4 7 -inf
    ^
stack: (-inf @ -1), (1 @ 1), (3 @ 2)

6 1 3 2 5 4 7 -inf
      ^
pop (3 @ 2): group size of 3 is (3 - 1) - 1 = 1
stack: (-inf @ -1), (1 @ 1), (2 @ 3)

6 1 3 2 5 4 7 -inf
        ^
stack: (-inf @ -1), (1 @ 1), (2 @ 3), (5 @ 4)

6 1 3 2 5 4 7 -inf
          ^
pop (5 @ 4): group size of 5 is (5 - 3) - 1 = 1
stack: (-inf @ -1), (1 @ 1), (2 @ 3), (4 @ 5)

6 1 3 2 5 4 7 -inf
            ^
stack: (-inf @ -1), (1 @ 1), (2 @ 3), (4 @ 5), (7 @ 6)

6 1 3 2 5 4 7 -inf
              ^
pop (7 @ 6): group size of 7 is (7 - 5) - 1 = 1
pop (4 @ 5): group size of 4 is (7 - 3) - 1 = 3
pop (2 @ 3): group size of 2 is (7 - 1) - 1 = 5
pop (1 @ 1): group size of 1 is (7 - (-1)) - 1 = 7
stack: (-inf @ -1), (inf @ 7)

What is this algorithm mapping coordinates to numbers called?

algorithm,coordinates,coordinate-systems,coordinate

So here's my question: does this algorithm exists already? Has it a name? This mapping is called the Z-order curve or Morton code: In mathematical analysis and computer science, Z-order, Morton order, or Morton code is a function which maps multidimensional data to one dimension while preserving locality of...

Getting Wrong Answer in “Longest non regular parentheses sub-sequence ”codechef june cook off

algorithm

See I know you will feel bad when I will tell you what is wrong in your answer. But the only thing wrong is you using gets(). Its 2015 no one uses it. I changed that to a scanf statement i.e delete this part of your code and get(s); get(s);...

Looking for a particular algorithm for numerical integration

algorithm,numerical-methods,numerical,numerical-integration

numerical integration always return just a number if you do not want the number but function instead then you can not use numerical integration for this task directly Polynomial approach you can use any approximation/interpolation technique to obtain a polynomial representing f(x) then integrate as standard polynomial (just change...

Given a sorted array and a parameter k, find the count of sum of two numbers greater than or equal to k

c++,arrays,algorithm,sum

There exists a rather simple O(n) approach using the so-called "two pointers" or "two iterators" approach. The key idea is to have two iterators (not necessarily C++ iterators, indices would do too) running on the same array so that if first iterator points to value x, then the second iterator...

Given length L find the shortest string formed only of as & bs >= L such that adding some character (Either a or b) doesn't produce a new palindrome

string,algorithm,palindrome

Here are my results so far: L=1-7: "aabbaba" -> "aabbabaa" (or the mirror, confirming your result) L=8: "aaabbaba" -> "aaabbabaa" (or the mirror) L=9: "aaaabbbaba" -> "aaaabbbabaa" (or the mirror) All futher L can be solved just by prefixing an additional a to the starting string....

Recursive solution doesn't iterate correctly

ruby,algorithm,search,recursion

The first time you enter the adjacencies[to_append].each, you immediately return from the method, therefore the loop will never be executed more than once. You need to return a list of phone numbers instead of just a single phone number build that list somehow in your recursive call ...

Knapsack with unbounded items

algorithm,dynamic-programming,knapsack-problem

One possibility would be to provide a suitable number of multiplicities of the items. For item i, there can be at most m_i := K / w_i choices of that item, where K denotes the knapsack capacity and w_i denotes the weight of the i-th item. Furthermore, for each weight...

Update minimum spanning tree if edge is added

algorithm,graph,tree,runtime,big-o

Don't know if your algorithm is correct, but it doesn't seem O(|V|) at least, because getting the "smallest edge not in T" of a vertex cannot be done in O(1). The most usual way to add an edge e=(u, v) into a MST T is: Run a BFS in T...

How to give mathemarical proof or support my answer through reasoning as a general case?

algorithm

This would be a hard real-time system - if a deadline is missed then a patient might die. As such, Algorithm B is the preferred algorithm because you can design the hardware around the n^2 worst case, whereas with Algorithm A the hardware must account for the n^4 worst case...

How to reduce time to find the n-th place from consecutive digits number for less than 1 second

php,algorithm,digits

What's important to realize is that it's easy to take big steps: 1 digit numbers: 123456789 - 9 * 1 digit 2 digit numbers: 101112...9899 - 90 * 2 digits 3 digit numbers: 100101102...998999 - 900 * 3 digits 4 digit numbers: ... Now you can do a recursive solution...

Reverse ^ operator for decryption

c,algorithm,security,math,encryption

This is not a power operator. It is the XOR operator. The thing that you notice for the XOR operator is that x ^ k ^ k == x. That means that your encryption function is already the decryption function when called with the same key and the ciphertext instead...

Find the shortest path sum in a matrix. Is Dijkstra not optimal for this case?

algorithm,go

Dijkstra should pass, I just make a submission using JAVA, and it took less than a second to complete each task. As I have mentioned, each value in the matrix can go up to 10^9, your solution can encounter a number overflow problem, which can effect the running time. My...

create specific permutation of a list in python [closed]

python,algorithm,permutation

l = [1,'a',12,'b','poppy'] def p(l,t): return [l[i-1] for i in t] print(p(l,(3,4,5,2,1))) [12, 'b', 'poppy', 'a', 1] indexing is 0 based so if you actually wanted to use the indexes for a 5 element list it would be (2,3,4,1,0) and [l[i] for i in t]...

Calculating completion time of scheduled dependent tasks

python,algorithm

Assume task 0 finishes at day 0. Add a new column to your table, "completion day". Go down the list of tasks, add the duration of the current task onto the completion day of the task it is dependent on. Store that as the current task's completion day. Find the...

Project Euler # 5; this solution works - but why?

c++,algorithm

Your logic does not work if(i%(ans%i)==0)ans*=(i/(ans%i)); else ans*=i; For example, if ans = 10 and i = 14, so, the lcm should be 70, but in your code, it is 140. The reason is, between ans and i , there are common divisors, but your code cannot detect that. For...

Should checking loop conditions be counted towards total number of comparisons?

c++,algorithm,sorting,c++11

If you look at your inserstion sort As you already put count =1 because as for exits on exit condition of for loop. for same reason then it also make sense that when while loop cancels the count++ inside will not get executed but there was a comparison made. but...

Understanding Big-Ω (Big-Omega) notation

algorithm,big-o

Big O,Theta or Omega notation all refer to how a solution scales asymptotically as the size of the problem tends to infinity, however, they should really be prefaced with what you are measuring. Usually when one talks about big O(n) one usually means that the worst case complexity is O(n),...

Hungarian algorithm in PHP with multiple assignments

php,algorithm,assign,subgraph,pairing-heap

So I finally found a valid way to achieve what was described in before. The solution: We make a column for each slot that is possibly given away. A cours has a amount of slots. We should have a number of columns, which is the sum of each amount of...

Determining if a graph has a cycle without using DFS

algorithm,graph,cycle,dfs

If and only if, at some point during kahn's algorithm has no source to choose (and the remaining graph is still none empty), there is a cycle Proof: Direction1 <--: If there is a cycle, let it be v1->v2->v3->vk->v1. At each step of the algorithm, none of v1,v2,...,vk is a...

Travels using graph

c++,algorithm,graph

Here is the graph I propose: Two kinds of vertices: departure vertex: airport+departure time arrival vertex: airport + arrival time. Two kind of edges: flight edge: from a departure vertex to an arrival vertex wait edge: from an arrival vertex to a departure vertex of later time in the same...

algorithm to get all combinations of splitting up N items into K bins

algorithm,recursion,permutation

A common approach is as follows. If you have, say, K bins, then add K-1 special values to your initial array. I will use the -1 value assuming that it never occurs in the initial array; you can choose a different value. So for your example the initial array becomes...

Removing a prior sample while using Welford's method for computing single pass variance

algorithm,math,statistics,variance,standard-deviation

Given the forward formulas Mk = Mk-1 + (xk – Mk-1) / k Sk = Sk-1 + (xk – Mk-1) * (xk – Mk), it's possible to solve for Mk-1 as a function of Mk and xk and k: Mk-1 = Mk - (xk - Mk) / (k - 1)....

How to print the right hemisphere of a square matrix

c++,algorithm,matrix

I think this should work for square matrices: void printHemisphere(int matrix[N][M], int n, int m) { int mid = n / 2; for(int i = 1; i < mid; i++) { for (int j = n - i; j < m; ++j) { std::cout << matrix[i][j] << " "; }...

How to apply ordering to a Scala Priority Queue?

algorithm,scala,priority-queue

If your elements are Ints, the easiest way to define such an Ordering is by taking a negative of the elements which should be ordered in reverse. You can create the Ordering, using methods provided by the object Ordering, and pass it to the PriotityQueue either explicitly: // I'm using...

Javascript: Detailed differences between !variable and variable == false?

javascript,algorithm

undefined is not a boolean value so when you use ! operator, your value will be converted to boolean at first. but == operator just checking your values. so if you want to get true from undefined == false you should do it like Boolean(undefined) == false ? 't' :...

Does there exist an algorithm for iterating through all strings that conform to a particular regex?

c#,regex,algorithm

Let's say the domain is as following String domain[] = { a, b, .., z, A, B, .. Z, 0, 1, 2, .. 9 }; Let's say the password size is 8 ArrayList allCombinations = getAllPossibleStrings2(domain,8); This is going to generate SIZE(domain) * LENGTH number of combinations, which is in...

Algorithmic big o order of growth code

algorithm,discrete-mathematics

The loops in fact only go up to the cube root of N. (i^3 < n, etc.) The 3 nested loops of this length, give O(cube root of N, cubed). This O(N) Of note, if you were correct and they each went to one third of N, then cubing this...

Update minimum spanning tree if edge is removed

algorithm,graph,tree,runtime,big-o

Since everything is still connected and only one edge has been removed, then most (and maybe all) of the spanning tree remains the same. Attempt to construct the same minimum spanning tree, and if the edge that was removed was part of the spanning tree, grab the next smallest edge...

Recursive algorithm that returns a bool when checking if array[i] == i (must be O(log n))

c++,arrays,algorithm,recursion

Do a regular binary search but with the (array[i] == i) condition instead of searching for a particular value. If (array[i] > i) move left else move right Of course this requires the values to be sorted, but your example indicates that is the case....

3 X 3 magic square recursively

c++,algorithm,math,recursion

Basically, you are finding all permutations of the array using a recursive permutation algorithm. There are 4 things you need to change: First, start your loop from pos, not 0 Second, swap elements back after recursing (backtracking) Third, only test once you have generated each complete permutation (when pos =...

Best way to extract ODD digits from a binary number

algorithm,bit-manipulation

I would go with performing Arithmetic Right Shift(till the length of the binary number) two at a time. This >> used in my logic is for arithmetic shift. (Note: In C language, right shifts may or may not be arithmetic!) Like, int count=0; bit=extractLastbit(binary_representation_of_the_number); while(count!=binaryLength){ // binaryLength is the length...

Dynamic programming: how to design algorithm for when there are two factors to consider?

algorithm,optimization,dynamic-programming,frequency

There is no need for Dynamic Programming for this problem. It is a simple sorting problem, with a slight twist. Find frequency / length for each file. This gets you, how frequent is each unit length access for the file. Sort these in descending order since each file is "penalized"...

Genetic Algorithm - convergence

java,algorithm,function,genetic-programming,convergence

I don't have the time to dig into your code but I'll try to answer from what I remember on GAs: Sometimes I will give it points that will never produce a function, or will sometimes produce a function. It can even depend on how deep the initial trees are....

Ranking with time weighting

python,algorithm,sorting,math

To clarify @Dan Getz and add @collapsar answer I will add the following: Dan's Formula is correct: (score1 * weight1 + ... + scoreN * weightN) / (weight1 + ... + weightN) The beauty of the weighted average is you get to choose the weights! So we choose days since...

How can I declare a counter inside of my recursive function? (Additive Persistence: Coderbyte)

javascript,algorithm,recursion

I'm going to extend @georg's answer and provide a full implementation var additivePersistance = (function () { function sumOfDigits (n) { var ret = 0; n.toString().split('').forEach(function (i) { ret += parseInt(i, 10); }); return ret; } return function additivePersistance (n) { if (n < 10) { return 0; } return...

strcmp performance in C

c,string,algorithm,data-structures

Yes, this is in O(n) in the average and worst case, where n is the length of the shorter of both given strings. You could also express that as O(min(m,n)) with m and n being the lengths of both strings, respectively. But no, O(n) doesn't mean that it needs exactly...

Simulating Fibonacci's Rabbits with multiple offsprings using python

python,python-2.7,dynamic-programming

The process for a single step is to replace all 'M's with 'MNNN' and all 'N's with 'M', so: def step(state): return ''.join(['MNNN' if s == 'M' else 'M' for s in state]) For example: >>> s = 'N' >>> for _ in range(5): print s, len(s) s = step(s)...

Disconnect all vertices in a graph - Algorithm

algorithm,graph

IIUC, this is the classic Minimum Vertex Cover problem, which is, unfortunately, NP Complete. Fortunately, the most intuitive and greedy possible algorithm is as good as it gets in this case....

C: sorted input serials

c,algorithm

The merge function is wrong, you did not consider when some part of a or b has leftover elements. void merge(int * a, int ac, int * b, int bc, int * out) { int i = 0, j = 0; while (i < ac && j < bc) {...

How to generate all partitions of a set

algorithm,set,combinatorics,backtracking

You can try the recursive answer if your set is not to big (or else use stack) : The principle is the following, you have a function that give back : rec_func(SET) = List of List of Set And work as follow : rec_func(SET) = if SET = {empty}: //...

Identify that a string could be a datetime object

python,regex,algorithm,python-2.7,datetime

What about fuzzyparsers: Sample inputs: jan 12, 2003 jan 5 2004-3-5 +34 -- 34 days in the future (relative to todays date) -4 -- 4 days in the past (relative to todays date) Example usage: >>> from fuzzyparsers import parse_date >>> parse_date('jun 17 2010') # my youngest son's birthday datetime.date(2010,...

Binary Search - Best and worst case

algorithm,data-structures

3. is indeed correct, as you will need to go through the algorithm and terminate at the "worst" stop clause, where the list is empty, needed log(n) iterations. 1. is not correct. The best case is NOT when the first element is the target, it is when the middle element...

Use Recursion to get Subsets of an array. C++ and Java give me different results

java,c++,algorithm,recursion,dfs

In the line res.add(temp); temp is a reference. You are adding a reference to the same list (itemList) every time you add it. Try changing it to something list res.add(new ArrayList(temp)); so that it copies the list instead....

Longest Increasing Subsequence code in O(N)?

python,algorithm,time-complexity,longest-substring

It's O(N) 'why to use DP of O(N2)' : You don't need to for this problem. Note, though, that you take advantage of the fact that your sequence tokens (letters) are finite - so you can set up a list to hold all the possible starting values (26) and...

coin change recurrence solution

dynamic-programming,recurrence,recurrence-relation

I don't really understand your recurrence relation: Let dp[i][j][k] represent sum up to i with j elements and k coins. I think you're on the right track, but I suggest simply dropping the middle dimension [j], and use dp[sum][coinsLeft] as follows: dp[0][0] = 1 // coins: 0, desired sum: 0...

Algorithm for [inclusive/exclusive]_scan in parallel proposal N3554

c++,algorithm,parallel-processing,c++14

Parallel prefix sum is a classical distributed programming algorithm, which elegantly uses a reduction followed by a distribution (as illustrated in the article). The key observation is that you can compute parts of the partial sums before you know the leading terms.

How to check whether the letters of a string exist in the given order within another string?

c++,algorithm

You may access out of bound memory while accessing key[counter] causing undefined behaviour. One possible fix is: for (int i = 0; i < s.size(); i++){ if (s[i] == key[counter]){ if(++counter == 5) break; // ^^ ^^^^ ^^^^^ } } or rewrite for as for (int i = 0; i...

Explain the time complexity of these grouping functions

c++,algorithm,inheritance,time-complexity

The first is supposedly in O(M*logN) time, where M is the size of the list, and N = number of concrete derived classes of Base It's not though. unordered_map is a hashtable, lookup and insertion have constant complexity on average. So the first is still O(M). Just with more...