Questions tagged [complexity]

Complexity is the analysis of how the time and space requirements of an algorithm vary according to the size of the input. Use this tag for reviews where the "Big O" is a concern.

Filter by
Sorted by
Tagged with
3
votes
3answers
2k views

Return the anti-diagonals

Give a N*N square matrix, return an array of its anti-diagonals. Look at the example for more details. Example: Input: ...
4
votes
5answers
1k views

Find The Duplicates in two arrays

Find The Duplicates Given two sorted arrays arr1 and arr2 of passport numbers, implement a function findDuplicates that returns an array of all passport numbers that are both in arr1 and arr2. Note ...
0
votes
2answers
334 views

Space complexity of the “add two binary strings” challenge

I was solving this problem of "adding two string binary numbers" and came up with the following algorithm. I am trying to analyze its time and space complexity. While I was satisfied with its time ...
1
vote
2answers
117 views

Finding duplicates in arrays

I'm given two sorted arrays, arr1 and arr2. They can either be of the same length or arr2 ...
3
votes
3answers
205 views

Finding the number of ways to partition {1,2, …, N} into p1 and p2 such that sum(p1) == sum(p2)

I am trying to write a space and time efficient algorithm to calculate the number of ways to partition a set of integers {1, 2, ..., N} into two partitions such that the sums of integers in the two ...
4
votes
1answer
625 views

Genomic Range Query in Python

Recently, I worked on one of the Codility Training - Genomic Range Query (please refer to one of the evaluation report for the detail of the task. The solution in Python is based on prefix sum, and ...
4
votes
1answer
122 views

2D discrete motion planner

I am writing a 2D discrete motion planner for a task with specific instructions. The instructions for the search algorithm are contained entirely in the docstring for the ...
-2
votes
1answer
77 views

Leet Code :: Merge Binary Tree :: Time Complexity [closed]

Problem Statement: Given two binary trees and imagine that when you put one of them to cover the other, some nodes of the two trees are overlapped while the others are not. You need to merge them into ...
-1
votes
1answer
1k views

Sort multidimensional array based of the difference in the value

Sort multidimensional array based of the difference in the value, if value is same sort on first column. Constrains: No of rows can be any but fixed no of column ie 2. Example: <...
3
votes
1answer
134 views

Binary search for IOI problem: Cave

Question http://www.ioinformatics.org/locations/ioi13/contest/day2/cave/cave.pdf Code ...
1
vote
0answers
1k views

Find the length of minimum sub array with maximum degree in an array

I tried solving a problem in Hackerrank which is to find the length of minimum sub array with maximum degree in an array. For example, consider the example {2, 2, 1, 2, 3, 1, 1} the min sub-array ...
1
vote
1answer
111 views

Comparing two n×m matrices

I have to do a pairwise compare of a couple of text files. They have the following format: ...
2
votes
0answers
48 views

RTB, SSPs is True 2nd Price Auction Program

I've created this program that is intended to check if SSPs in RTB auctions run true second price auction. The program is running properly and returning the values as desired. I would like to get ...
3
votes
2answers
932 views

Most popular element with count in Array with Java

Here is the input array of int values Example: { 5, 4, 6, 5, 1, 0, 7, 7, 3, 5 } Find the most repeated element with its count, example output; ...
2
votes
1answer
242 views

Find all pairs in an array whose absolute difference equals x

I have an array A of integers with n values and an integer x. I need to find all the pairs in that array whose absolute ...
4
votes
2answers
106 views

Adding input strings and finding occurrences of certain prefixes

A user inputs data using a keyword add word and when he wants to find words with particular prefix then he enters find keyword. ...
4
votes
2answers
306 views

Design a O(1) data structure

How would I implement a data structure that supports the following in constant time? I got this question at a job interview, and the following is my solution. Please check my approach, or suggest a ...
5
votes
1answer
417 views

N queens variation recursion Python 3

I am trying to solve a modified version of the N-queens problem, where the addition is that for any NxN board (3<=N<=12) there are M holes (0<=M<=N^2) that are placed at random (but given) ...
1
vote
1answer
61 views

Given an array of integers, find and print its number of negative subarrays on a new line

Given an array of N integers, find and print its number of negative subarrays (i.e sub arrays having negative summation) on a new line. My code is taking \$\mathcal{O}(n^2)\$ time. How can I improve ...
1
vote
2answers
498 views

Adding Combinations of Numbers in an Array

Could someone help me optimize this code for time complexity? What is the best way to do this that doesn't include nested for loops? Take an array of integers and return a list of sums of every ...
2
votes
2answers
983 views

Python PEMDAS calculator [closed]

The goal of this calculator is to evaluate an expression with PEMDAS in mind (no parenthesis yet, adding soon). Although the program works, I want to make it as efficient as possible with the approach ...
10
votes
4answers
1k views

Maximum consecutive subarray sum for a variable sliding window size

The Problem: Given an array of integers L find the largest sum of a consecutive subarray of size k or less. Constraints: ...
4
votes
3answers
3k views

Sort a stack of numbers in ascending order only using push

I have a stack of numbers ranging from 1 to 1 million representing a pile of numbered DVDs. Given the stack in random order I am to sort the stack by only taking an element from the stack and push it ...
-3
votes
1answer
2k views

Counting the number of ways to break an amount into coins

I have an algorithm here that counts the number of ways that n cents can be represented using the following denominations: quarter: 25 cents dime: 10 cents nickel: 5 cents pennies: 1 cent There are ...
-5
votes
1answer
210 views

Category of sorting algorithm and complexity [closed]

Just for fun, I wrote a sorting algorithm. I did not compare this with existing sorting algorithms.Can someone tell me what class of sorting algorithm this is and it's complexity? The algorithm ...
3
votes
1answer
3k views

Calculating the most profit from an array of stock prices

I'm a newbie learning how to code, and I am trying to find the most efficient way to calculate the most profit from an array of stock prices. For a given array,I have a list of stock prices over n ...
2
votes
1answer
2k views

Implementation of Prim's Algorithm to find minimum spanning tree

What is the time complexity of the following code? I'm implementing Prim's Algorithm with adjacency matrix representation of the graph and priority queue. ...
1
vote
1answer
57 views

Two approaches to count occurrences of one char in a String in Java

I have two approaches: First Approach: ...
5
votes
1answer
954 views

MaxCounters solution

I am doing this Codility problem You are given N counters, initially set to 0, and you have two possible operations on them: increase(X) − counter X is increased by 1, max counter − all ...
5
votes
2answers
1k views

Non-recursive implementation of MergeSort

I've been trying to internalize some of the basic sorting algorithms recently, and to do so I've been looking at their wikipedia pages to refresh myself with how they work, and then coding my own "...
-1
votes
1answer
2k views

Finding the distance from each array element to the nearest zero entry

I wrote a program, that gets a certain array and replaces each value in the array with the distance from it to the closest zero value. Time complexity is \$4n\$ => \$O(n)\$. (please correct me if I'm ...
10
votes
2answers
5k views

Fish Food Chain of complexity O(N)

I understand that if you don't know the trick, it's not easy create a solution with a complexity of \$O(N)\$. However, I would like to ask you how to solve this tricky question: You are given two ...
4
votes
4answers
1k views

Find element that has been removed from a shuffled array

For a function to determine which element has been removed from a shuffled array, I came up with: ...
2
votes
1answer
5k views

HackerRank: Left Array Rotation in Python

Here is the problem on HackerRank. I want to know how I can improve this code. I am mainly trying to improve the following skills: Documentation, functional programming (top-down approach), accurately ...
-4
votes
1answer
857 views

What are the time and space complexity of this algorithm? [closed]

What is the time and space complexity of this algorithm and can it be improved (how)? It generates random 4 digit even number and the adjacent 2 digits must be different. ...
4
votes
1answer
83 views

Make each element equal to its neighbouring element which is maximum in a matrix

I have a matrix and I want to make each of its element equal to the maximum of its neighbouring element and each time I increase number of counts till all the elements in the matrix becomes equal to ...
1
vote
1answer
121 views

Merge sort C# time and space efficiency

Please comment on time and space efficiency. ...
0
votes
1answer
341 views

Test whether two strings are anagrams of each other

What is the time/space complexity of this algorithm which checks if two strings are anagrams? My guess is that time is \$O(n)\$ and space \$O(1)\$ but I am not sure. Can it be improved? ...
4
votes
2answers
298 views

Find lexicographical permutations

I have tried many possible methods here but I am still not able to reduce the time complexity of below algorithm. The basic layout of my problem is as follows: I have a string that is composed of ...
3
votes
2answers
855 views

Checking if a LinkedList is a palindrome

I would like to know if my code is \$O(n)\$ space complexity. The code checks if a doubly linked list is Palindrome. ...
7
votes
3answers
1k views

Find the total number of ways W, in which a sum S can be reached in N throws of a dice

I was solving this question: Given there is a 6 sided dice. Find the total number of ways W, in which a sum S can be reached in N throws. Example: S = 1, N = 6 => W = 0 S = 6, N = 6 => W ...
3
votes
1answer
45 views

Complexity for two approaches of finding next biggest palindrome of a number

I have come up with a problem online about the next biggest palindrome of a number and i have solved the problem by two different approaches in python. The first one is, ...
1
vote
2answers
3k views

Print Z pattern from 2D String array

I am trying to print the Z pattern, but the time complexity is coming to \$O(n^2)\$. Is there any way to reduce the time complexity? ...
3
votes
1answer
73 views

Dividing a ThreadPool class into component classes to reduce/isolate complexity

I have a ThreadPool class which has grown to a point where it is becoming difficult to keep all of this unit of work in mind. It is also becoming harder to read. ...
5
votes
1answer
6k views

Sort a given string in ascending order

This code sort the string below in ascending order. I'd prefer it split-up in two or three smaller, simpler methods. I'm also wondering whether my algorithm has a decent time complexity. Given ...
4
votes
2answers
263 views

Checking whether one string is a permutation of another

I solved the standard "write a method to determine if one string is a permutation of the other" question with the following code, using xor, ...
3
votes
1answer
2k views

Finding the maximum distance from the starting node

I've tried everything to make my program faster but with 250 nodes my code takes around 9 seconds to print the result, and with 5000 nodes it took around 260 seconds. Is there a way to make my ...
5
votes
2answers
971 views

JavaScript function for finding perfect numbers

The following function has been created for finding "Perfect Numbers". About Perfect Numbers: Wikipedia ...
7
votes
3answers
2k views

A partition algorithm for positive integers

I have encountered the following problem that I found very interesting to solve: Given an array of positive integers {a1, a2, ..., an} you are required to partition the array into 3 blocks/...