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
49
votes
12answers
20k 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 ...
22
votes
3answers
30k 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 ...
15
votes
2answers
786 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 ...
13
votes
7answers
1k 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 ...
13
votes
5answers
8k 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 ...
13
votes
4answers
3k 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 ...
13
votes
1answer
299 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 ...
13
votes
1answer
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 ...
12
votes
3answers
1k 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 <...
12
votes
1answer
1k 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 ...
11
votes
5answers
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 ...
11
votes
3answers
1k 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: ...
11
votes
5answers
16k 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 ...
10
votes
8answers
12k views

Calculate square of a number without multiplication

I wrote these two methods to calculate the square of a number: ...
10
votes
6answers
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. ...
10
votes
2answers
4k 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 ...
10
votes
2answers
556 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 ...
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: ...
10
votes
2answers
417 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 ...
9
votes
4answers
14k 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 ...
9
votes
1answer
1k 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 ...
8
votes
3answers
297 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 ...
8
votes
2answers
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....
8
votes
1answer
847 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 - ...
8
votes
3answers
351 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 ...
8
votes
1answer
157 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-...
8
votes
1answer
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 ...
8
votes
3answers
698 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 ...
8
votes
2answers
4k 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 ...
8
votes
1answer
96 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'...
8
votes
2answers
8k 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 ...
8
votes
1answer
174 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 ...
8
votes
2answers
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: ...
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 ...
7
votes
6answers
11k 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 ...
7
votes
5answers
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 ...
7
votes
3answers
4k 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 ...
7
votes
1answer
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 ...
7
votes
3answers
841 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 ...
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/...
7
votes
2answers
5k 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 ...
7
votes
1answer
662 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(...
7
votes
1answer
2k views

Check for valid parentheses nesting

I found this question on leetcode and that was my answer ... But someone told me it's too bad that it takes \$O(n^3)\$ I am not sure that it takes all that time ... and trying to find better ...
7
votes
2answers
745 views

Finding pairs of numbers within A that add up to N

I am working on an interview question from Amazon Software Interview: Given an integer N and an array of unsorted integers A find all pairs of numbers within A which add up to N I have a working ...
7
votes
1answer
10k 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 ...
7
votes
1answer
176 views

Check consistency of a list of statements, with fuzzy rhyme matching

I made a program today that solves the following problem on a programming competition site (open.kattis.com): Check if all statements with the following format X is Y or X not Y are consistent. X and ...
7
votes
1answer
204 views

Extending the extended Stable Marriage Problem using a Python class

As soon as I saw this open source paper, I thought that the best way to replicate their code would be using a python class. After having replicated and extended the ...
6
votes
5answers
11k 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): ...
6
votes
4answers
1k views

Sufficient implementation of subset sum for 45 min interview

I am preparing for interviews, and have implemented a solution to this problem from Geeks for Geeks: Given a set of non-negative integers, and a value sum, determine if there is a subset of the ...
6
votes
2answers
1k 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 ...