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
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 ...
1
vote
0answers
207 views

Parsing URL query strings in AngularJS

Here are two very small blocks of code I wrote while trying to fix a bug in AngularJS. Both do the same thing. I'm trying to understand how the two differ, mainly in terms of the tradeoff between cpu ...
2
votes
1answer
97 views

Random permutation with defined order of last occurrences

This Python function takes two arguments: chr_list which is a mutable sequence of characters c ...
2
votes
2answers
88 views

High execution time on number partitioning program in Python 2.7

I am writing a program to count only the partitions of a number with distinct parts. I am using a bottom-up approach to dynamic programming to generate partition lists from previously obtained ...
7
votes
1answer
181 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
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 ...
4
votes
2answers
363 views

Split DAG into disjoint sets

I wrote an algorithm to separate a DAG into disjoint sets of vertices. I was hoping to have some comments on algorithmic complexity and efficiency of the Python code. Notably, I don't like the adding ...
6
votes
1answer
5k views

Stable radix sort in-place using O(1) space

I am trying to implement a stable radix sort in place with O(1) space. I've seen Wikipedia, and I notice the C implementation is using a temporary variable to hold the sorted value for each pass, and ...
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 ...
5
votes
2answers
168 views

Does my Linklist implementation have memory leaks?

Are there any memory leaks in this linklist implementation.Also is the implementation correct?Can the time complexity be optimized? ...
1
vote
1answer
61 views

Finding the distance between every indices in an array that contain odd numbers

I'm doing this HackerRank problem which basically boils down to what I've written in the title. We have to find out the distance between all the odd values in the array. I've written this code below ...
4
votes
1answer
889 views

Lexicographically smallest wave like array without sorting

Given an array of integers, sort the array into a wave like array and return it. In other words, arrange the elements into a sequence such that a1 >= a2 <= a3 >= a4 <= a5..... Example: Given [...
2
votes
1answer
565 views

Taxicab numbers algorithm check

With the programming language skills that are available to me at the time, I've written this program to find the "taxicab numbers" (e.g. a number expressible as the sum of two cubes in two different ...
1
vote
0answers
89 views

SPOJ Aliens in a Train

I need to find the largest interval with a value less than a limit Lt. The data is as follows: For every test case T: Number of elements N, limit Lt N number of elements data I wrote the ...
3
votes
1answer
2k views

Finding line numbers of duplicate lines in a log file

I have a log file with a million lines, and my task is to code something that outputs the lines that have duplicates, and the line numbers. I've thought of two ways to approach this : 1) Use python'...
2
votes
0answers
868 views

Word Wrap via Dynamic Programming

Word Wrap problem in short: Given n words and a line length, break the words into lines in such a manner that minimizes the sum of the costs of all the lines. Consider the cost of each line being (...
1
vote
2answers
231 views

Massive file sorting algorithm

I was trying to sort a massive file of successive chars in C. I did some research and found a few file sorting algorithms that look the same. Their main idea is to read an amount of data to memory, ...
-1
votes
1answer
7k views

Complexities: Filtering out nested array inside an array

I am doing some iteration over an array which have another set of array (the nested array). I need to .map() the outer array in such a way that it should filter out ...
2
votes
1answer
2k views

Find the longest subarray with sum less than K

The problem consist of finding the longest contiguous subarray with a sum less than a given integer K. The input data are: K - ...
3
votes
1answer
968 views

Calculating binary tree height as asked in the interview

Input: The first line contains the number of vertices \$n\$. The second line contains \$n\$ integer numbers from the range \$\left[−1, n − 1\right]\$ representing the \$0\$-based index of the ...
0
votes
1answer
861 views

Subset sum simple iterative implementation

Here is the simplest iterative implementation of Subset sum problem that I could come up with1, as a follow up to this recursive implementation of the same problem: ...
4
votes
1answer
277 views

Modified Z-Algorithm for string similarity with one char difference

I have modified a Z-Algorithm for string similarity in order to match strings which differ in 0 or 1 char. However, it seems much slower than original Z-Algorithm although from my point of view there ...
2
votes
1answer
124 views

Infinite Monkey Theorem Python Comparison

I wrote code to demonstrate the Infinite Monkey Theorem which states that if a monkey types at a keyboard for an infinite amount of time it will almost surely type a given text such as William ...
3
votes
1answer
497 views

Stack which finds the minimum element

Write a program to implement stack which implements min a method which gives the minimum element below the top element in the stack. ...
3
votes
3answers
360 views

URLIfy a character array using Python - follow-up

This is a follow up to my last code review: URLify a string using Python This problem has been reviewed in other languages, but I tried to solve this without looking at those answers. I am hoping ...
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 ...
3
votes
1answer
46 views

Creating List of String elements that occur a certain amount of times using only the List ADT

I am tasked with creating a list with no duplicates of all String elements, in this case first names, of an ArrayList. The method is passed a threshold, and the ...
1
vote
1answer
714 views

Finding a max element in an array in Java

Created the following method: ...
2
votes
1answer
2k views

Iterative solution for generating all permutations of a string

I know the runtime for generating all permutations is supposed to be \$O(n!)\$. I'm not sure if the code I wrote for it runs in \$O(n!)\$ though. I'm having trouble analyzing its runtime. The ...
5
votes
2answers
221 views

Function to check truth value of a specific statement

I want to check the truth of A + B - (A & B) == A | B for N-bit numbers. For example, here's a "truth" table for 2-bit numbers. (I know I'm taking liberty with ...
3
votes
1answer
337 views

Count Acute, Right and Obtuse triangles from n side lengths

Problem Statement: We have \$N\$ sticks. The size of the \$i\$th stick is \$A_i\$. We want to know the number of different types of triangles created with each side from a single different stick. ...
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: ...
4
votes
2answers
244 views

TopCoder problem “Substitute” - SRM 160 (Division II Level One)

I have solved the problem "Substitute" at Topcoder. A simple, easy to remember system for encoding integer amounts can be very useful. For example, dealers at flea markets put the information about ...
2
votes
0answers
215 views

Improving time efficiency of finding maximum area rectangles in a histogram

Here's my solution but I am looking for ways to improve the time complexity of solution. Also this question is categorized as being solved by stack so I would like to know how to approach it using ...
10
votes
2answers
418 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 ...
3
votes
1answer
2k views

Faster palindrome checker in Java

I wonder if there could be a faster palindrome checker in Java. The best one I have is O(n/2) which is O(n) eventually: ...
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 ...
4
votes
2answers
87 views

Given a set of random strings, write a function that returns a set that groups all the anagrams together in objective-c

I would like to get feedback on the solution and a question regarding Big O. I am first converting each character in the string into the array and that would be O(n) then i am sorting the array O(n ...
10
votes
8answers
12k views
7
votes
6answers
12k 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 ...
1
vote
2answers
143 views

Summing all keys in the leaves of a tree

My program takes 35 sec to run example 2. How can I make my program faster? ...
4
votes
1answer
13k views

Permutations of any given numbers

I have solved one programming problem where we have to find all the permutations of given numbers. For example, \$[1,2,3]\$ have the following permutations: $$[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,...
-5
votes
1answer
109 views

Reverse a string [closed]

I use this for reversing a string, but it has O(n) : reverse(y.begin(),y.end()); How can I reverse a string in O(n/2) ?
0
votes
2answers
13k views

Replace spaces in string

...
4
votes
1answer
211 views

Local variable lookup table

I'm currently in the process of writing my own programming language and the Virtual Machine for the language is responsible for handing all of the local variable scopes. I need to support the ...
1
vote
1answer
56 views

Return Object[] while connecting to DB once

I have written this code according to my requirements. But after finishing the code, it looks like there are too many loops. I have reduced it as much as I can. Can you find any improvements that I ...
3
votes
0answers
143 views

ACM-ICPC HackerRank challenge in C++

I was doing a programming question in C++ at HackerRank. Given a set of up to 500 bitstrings, each up to 500 bits long, the task is to find the pair a and b such that the bitwise OR contains the most ...
3
votes
1answer
79 views

Sum to zero of all triples in a list - n^2 running time

As part of an interview, I had to submit a code sample to solve the classical "triples sum to 0" problem. The reviewer said the algorithm needed to be in n2 time, and I was later informed that the ...
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....
4
votes
1answer
1k views

Find given number by summing up integers from 2 sorted arrays

I am working on an algorithm question in which I need to find out pair of number out of 2 sorted arrays which sum up to the given number. I need to print out the indexes of those pairs rather than ...