# 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.

343 questions
Filter by
Sorted by
Tagged with
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 <...
57 views

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

I have two approaches: First Approach: ...
898 views

### Find all occurrences of all permutations of a shorter string within a longer string

Input is two strings, the first string being the long string and the second smaller string being the permuted string. The output should return the starting indices of all occurrences as well as the ...
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 "...
856 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. ...
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 ...
121 views

### Merge sort C# time and space efficiency

Please comment on time and space efficiency. ...
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? ...
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 ...
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. ...
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 ...
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? ...
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, ...
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 ...
262 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, ...
968 views

### JavaScript function for finding perfect numbers

The following function has been created for finding "Perfect Numbers". About Perfect Numbers: Wikipedia ...
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 ...
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 ...
76 views

### One-off string detection

Problem spec from CareerCup. Given two strings, return boolean True/False if they are only one edit apart. Edit can be insert/delete/update of only one character in the string. Eg. True xyz,xz xyz,...
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 ...
180 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 ...
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 ...
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 ...
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 ...
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: ...
949 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 ...
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 ...
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 [...
563 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 ...
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 ...
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. ...
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'...
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 (...
230 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, ...
238 views

### Finding substrings within arrays

I need to find the substrings within my array. If I have an array: ["abc", "abcd", "abcde", "xyz"], my method should return the array members: ...
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 ...
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 - ...
6k views

### Find the number of K-Complementary pairs in an array

Below is the program to find k-complementary pairs: K = A[i] + A[j];. ...
965 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 ...
860 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: ...
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 ...
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 ...
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 ...
2k views

### 'Zero out' a matrix using Python

Below is my code for an attempted solution to cracking the coding interview exercise 1.8 written in python 3.5. The problem statement is: Write an algorithm such that if an element in an MxN ...
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 ...
8k views

### Simple string compression in Python

This is my solution to exercise 1.6 in Cracking the Coding Interview. I am interested in receiving feedback on the coding style and time/space complexity. The exercise statement is: Implement a ...
3k views

### Check if two strings are one 'edit' apart using Python

The code below is my solution in python 3 to exercise 1.5 in Cracking the Coding Interview. I would appreciate feedback on both the algorithm (improvements to space and time complexity) and/or coding ...
4k views

### Check if a string is a permutation of a palindrome using Python

This is a solution to exercise 1.4 from Cracking the Coding Interview written using Python 3. Given a string, write a function to check if it is a permutation of a palindrome. Example: 'Tact Coa' ...