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
53 votes
12 answers
22k views

Searching in an array in less than O(n) time

I have an array where each element is either one less or one greater than the preceding element \$\{x_i = x_{i-1} \pm 1\}\$. I wish to find an element in it in less than \$O(n)\$ time. I've ...
user3011937's user avatar
24 votes
9 answers
6k views

The fastest way to find one unique value when all other values are the same

I have completed this question and I am wondering what is the fastest way to solve it. The question is "There is an array with some numbers. All numbers are equal except for one. Try to find it!&...
Jacques's user avatar
  • 343
22 votes
3 answers
33k views

Find all paths from source to destination

Given a directed connected graphs, find all paths from source to destination. Looking for code review, optimizations and best practices. Also need help figuring out complexity, which in my best ...
JavaDeveloper's user avatar
15 votes
2 answers
1k views

'Team Split' problem

Below is my solution for this 'Team Split' problem. In summary, the problem is to find relative strength of 2 teams by finding the difference between their total strength (individual strengths can be ...
arunkrishnamurthy01's user avatar
14 votes
1 answer
2k views

Nonogram puzzle solution space

I've written some code to brute-force enumerate the solution space of nonogram puzzles up to a certain size. It does a good job up to the first ~4 billion puzzles, but I run out of disk space to store ...
user avatar
13 votes
7 answers
2k views

Finding the most popular element with C# given O(1) space complexity requirement

I have tried to solve the following problem in C# with LINQ: Given an integer array, find the most frequent number and it's count in the array. If multiple numbers have the same highest frequency ...
tugberk's user avatar
  • 295
13 votes
5 answers
9k views

"Algorithmic Crush" problem hitting timeout errors

This is the HackerRank problem Algorithmic Crush: You are given a list of size N, initialized with zeroes. You have to perform ...
enthusiastic's user avatar
13 votes
4 answers
6k views

Check if one string is a permutation of another using Python

The code below is an attempt at a solution to an exercise from the book "Cracking the Coding Interview." I believe that the worst case time complexity of the code below is \$O(n)\$, where n is the ...
Average's user avatar
  • 841
13 votes
1 answer
2k views

Extended stable marriage challenge

I've written a solution for the stable marriage problem in the case that the number of men is not equal to the number of women. My problem is not that I can't prove my code is right. The problem is I ...
Arman Malekzadeh's user avatar
12 votes
3 answers
2k views

Given some integers, return the k most frequent elements

Given a non-empty array of integers, return the k most frequent elements. For example, given [1,1,1,2,2,3] and k = 2, return <...
Stack crashed's user avatar
12 votes
1 answer
2k views

Seating Students (partitioning sort of)

The goal of this code is to seat students in a classroom based on a single test score. We want students to be evenly distributed across the class such that every student is positioned next to the ...
iVinny's user avatar
  • 121
11 votes
5 answers
1k views

Refactoring my problem-solution to reduce complexity

I need some help refactoring my solution to the problem below: Problem Statement An Association of Computer Scientists meets on a weekly basis. There is a certain number of seats in the meeting room ...
Stefan Pavikevik's user avatar
11 votes
5 answers
2k views

Are the sum of two numbers desired?

Given two input arrays [-1, 8, 3] and [3, 7, 2] your function will return true if any two of the numbers in the first array add ...
Ugur Yilmaz's user avatar
11 votes
5 answers
18k views

Checking if three numbers sum to a given number

I'm working on the following interview practice problem, and got the following solution, which runs in worst case n! time (best case constant), and I'm trying to ...
Brandon's user avatar
  • 213
11 votes
3 answers
2k views

Finding Pythagorean triplet in array

We have an integer array as: private int[] arr = {1, 3, 5, 14, 18, 29, 78}; We have a function which takes three inputs of the array and checks whether: ...
WISHY's user avatar
  • 213
11 votes
4 answers
2k 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: ...
alecxe's user avatar
  • 17.2k
10 votes
8 answers
13k views

Calculate square of a number without multiplication

I wrote these two methods to calculate the square of a number: ...
user avatar
10 votes
6 answers
3k views

Getting filtered autolist

Is there a better way to write the following code fragment? I can't have more than 10 conditional statement in my method as it gives cyclomatic complexity. ...
Zeeshan's user avatar
  • 203
10 votes
4 answers
19k views

Finding overlapping time intervals

You have two lists with meetings scheduling (start time, end time). Meetings in single list don't intersect. Find all intersecting meetings across the two lists. Is my complexity \$O(N M)\$? If I use ...
Gilad's user avatar
  • 5,321
10 votes
2 answers
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 ...
Thor's user avatar
  • 143
10 votes
2 answers
586 views

Minimum sub-array challenge

Below is my solution to finding the minimum product sub-interval. It passed 8/12 or so test cases, but the other test cases timed out if they hadn't finished within 2 seconds. When I compile this code ...
codeReview's user avatar
10 votes
2 answers
452 views

Min sub array size with a given sum

How can the time complexity of the following code be improved (assuming it's \$O(N^2)\$)? What about style and patterns? This code is trying to find the minimum subarray size that adds up to given sum ...
Mona Jalal's user avatar
9 votes
3 answers
4k views

Find the smallest positive integer that is absent from a given array

I made the acquaintance of big-O a couple of weeks ago and am trying to get to grips with it, but although there's a lot of material out there about calculating time complexity, I can't seem to find ...
half of a glazier's user avatar
9 votes
2 answers
2k views

Solving 'decent numbers' that follow specific division rules

HackerRank Problem Statement I have to find the largest 'decent number' having N digits. A decent number has the following properties: 3, 5, or both as its digits....
benSooraj's user avatar
  • 305
9 votes
2 answers
9k views

URLify a string using Python

I have been working my way through the exercises in the book Cracking the Coding Interview. I wanted to get feedback for the following exercise. Write a method to replace all spaces in a string ...
Average's user avatar
  • 841
9 votes
1 answer
2k views

Codility MaxCounters peformance in Python capping out at 77% performance

My problem is quite similar to the question found here, except I am attempting to answer the question in Python. Given an array of N counters, all initialized to 0, and an array ...
optical_anathema's user avatar
9 votes
1 answer
15k views

Rotate Matrix using Python

This is my solution to Exercise 1.7 from Cracking the Coding Interview. I would appreciate any feedback on coding style and algorithm efficiency. I do know that there is an existing function in ...
Average's user avatar
  • 841
8 votes
6 answers
13k views

Find maximum difference between values in an array

My task is to use the following pseudocode and improve it (make it run faster). Also I have to analyze the runtime of the given pseudocode and of my new code that i improved. What does this algorithm ...
Shahbaz's user avatar
  • 89
8 votes
2 answers
3k views

Sum the exponents of the prime factors of a number

My goal is to find the sum of the exponents of the prime factors of an integer. I wrote the code below with the complexities specified here (I am not 100% sure of the complexities though): Runtime ...
giulio's user avatar
  • 743
8 votes
1 answer
919 views

Regular Expression Evaluator

Task to be accomplished: Write a function that takes two strings s and p as arguments and returns a boolean denoting whether s matches p. p is a sequence of any number of the following: a-z - ...
Mohammad Areeb Siddiqui's user avatar
8 votes
3 answers
391 views

Calculating the mean differences of subarrays

I'm trying to devise a way to calculate the mean differences (the absolute average differences between any two values in a set), of sub-arrays (starting from arbitrary indices) in an ...
Kevin's user avatar
  • 197
8 votes
1 answer
205 views

An array with \$O(\log\ n)\$ time complexity for all operations

Does this exist already? It's an array (=variable-size list with integer indices) where add/remove/set and get all take \$O(\log\ n)\$ time. I couldn't find this anywhere, so I made up the name "Log-...
Stefan Reich's user avatar
8 votes
1 answer
1k views

Finding largest subset of line segments that don't intersect

I completed a challenge of codeeval called BayBridges. It can be found here. I have uploaded my code on GitHub here. In summary, the challenge is to take a list of line segments, each specified by ...
mrbubz's user avatar
  • 83
8 votes
2 answers
5k views

Finding the count of negative sub-arrays for a given array

I want to improve my implementation for the following problem: You are given an array of n integers. A sub-array is "Negative" if sum of all the integers in that ...
John Doe's user avatar
  • 245
8 votes
2 answers
12k views

Finding the largest repeating substring

Here's my code that takes a large string, and searches for the longest reoccurring substring. It compares the first letter with every other until it finds a match, then saves it. Then it compares the ...
Andrew Tsay's user avatar
8 votes
3 answers
2k views

Longest 'balanced' substring

I was given a task where given a string of '0's and '1's, return the longest substring where the count of '0's and '1's are equal. I was told also that the code should be O(n) and space O(1). Below ...
anon582847382's user avatar
8 votes
1 answer
114 views

Joining collections... because it's fun

I'm working on a LinqEnumerable class (reviewable here), and I'm no Big-O expert and I'm pretty bad with algorithms, so I wonder what the complexity is for what I'...
Mathieu Guindon's user avatar
8 votes
2 answers
2k views

Codility "max slice swap" challenge

Problem Description: Find the maximum sum of a compact subsequence of array elements after performing a single swap operation. Solution: ...
Jay's user avatar
  • 271
8 votes
1 answer
223 views

Compute the height of a tower made of buckets

I need to speed up my algorithm. It is about finding the height of a tower. The tower is built from buckets. Each bucket has height and radius (1 <= height,radius <= 1000). Variable ...
Th3NiKo's user avatar
  • 83
7 votes
5 answers
17k views

Finding the most common character in a string with a hash map

I created a method for finding the most common character in a string (using HashMap): ...
Roey Cohen's user avatar
7 votes
3 answers
2k 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 ...
Harsha's user avatar
  • 1,291
7 votes
5 answers
2k views

Finding unique triplets adding up to 0

I am working on a problem "3Sum", in which, given an array S of n integers, are there elements ...
chmod766's user avatar
  • 131
7 votes
2 answers
2k views

Google's Python exercise about lists very different from the given solution

I found some Python exercises that were made by Google in their Python classes and decided to spend some time with them. Given the following description: E. Given two lists sorted in increasing order,...
streppel's user avatar
  • 635
7 votes
3 answers
8k views

Algorithm to compute the n-th derivative of a polynomial in Python

As a personal exercise, I'm trying to write an algorithm to compute the n-th derivative of an ordered, simplified polynomial (i.e., all like terms have been combined). The polynomial is passed as an ...
lnNoam's user avatar
  • 173
7 votes
2 answers
2k views

Simplify function to sum the absolute value of the difference between all pairs of elements of a sorted array

Given a sorted array of N elements, I need to find the absolute sum of the differences of all elements. Given 4 elements (1, 2, 3 and 4): |1-2|+|1-3|+|1-4|+|2-3|+|2-4|+|3-4| = 10 Here is my code ...
Sushim Mukul Dutta's user avatar
7 votes
2 answers
775 views

Best Algorithm for solving USACO: Photoshoot - Python

I was trying to solve this problem with Python 3.8. I couldn't find a way other than to brute-force calculate all the possible permutations then check which permutation was valid. The program works ...
12 rhombi in grid w no corners's user avatar
7 votes
3 answers
906 views

Finding the shortest excerpt that contains all search terms

Write a function called answer(document, searchTerms) which returns the shortest snippet of the document, containing all of the given search terms. The search ...
python's user avatar
  • 623
7 votes
1 answer
738 views

Determine total number of ways of reaching a destination

Question: One of Scotland Yard’s most wanted criminal (Mister X) is on the run and needs to reach a certain destination safely. There are three modes of transport available for him - By air, ...
darthShadow's user avatar
7 votes
2 answers
147 views

Determine the complexity of sorting a binary array

The challenge is to sort an integer array containing only ones and zeros with the lowest complexity possible. As always, I am interested in any improvements suggested but in this question I am most ...
amalgamate's user avatar
7 votes
1 answer
812 views

Monitoring the recursive growth of a zombie rabbit population

Breeding like rabbits Write a function answer(str_S) which, given the base-10 string representation of an integer \$S\$, returns the largest n such that \$R(...
python's user avatar
  • 623

1
2 3 4 5
9