# 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
170 views

### Subset Sums in Java

Given an array of integers, print sums of all subsets in it. Output should be printed in increasing order of sums. Input : arr[] = {2, 3} Output: 0 2 3 5 Input : ...
2k views

### Sort an array of 0s, 1s and 2s in Java

Write a program to sort an array of 0's,1's and 2's in ascending order. Input: The first line contains an integer 'T' denoting the total number of test cases. In each test cases, First ...
487 views

### Alone in a Couple implementation in Java

In a party everyone is in couple except one. People who are in couple have same numbers. Find out the person who is not in couple. Input: The first line contains an integer $T$ denoting ...
71 views

### Finding the horse number you will get

I got this question from the interviewbit site test. There are n horses and you are the kth person in the line to ride on the horse. All the persons in the queue will go with the lowest numbered ...
375 views

### List of Ordered pairs from unordered Pair in Java

Problem statement is Write a method that can take an unordered list of airport pairs visited during a trip and return the list in order. ...
300 views

### Moore-Neighbor Tracing Algorithm

I wrote code to extract the contour of a hole, based mostly on the Moore-Neighbor Tracing algorithm. Only a. instead of finding a shape, I'm finding a "hole"; and, b. I'm looking for the (outer) ...
248 views

### Reversing the vowels in a String

Given a string, reverse only the vowels present in it and print the resulting string. Input: First line of the input file contains an integer T denoting the number of test ...
732 views

### JavaScript Determine if Number is Lucky

A challenge from Code Fights; a function that takes a number no less than 10 and that will always have an even number of digits and determines if the sum of the first half of the digits equals the sum ...
99 views

### Possible letter combinations of a dial pad in linear time using a recursive approach

Time complexity: I walk the initial unzipped array of keys representing the number O(N) backwards. I then do an inner walk of the proceeding array of letters *O(L^2), mapping it to every value in the ...
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 ...
112 views

### Anagram checking implementation

Given two strings, check whether two given strings are anagram of each other or not. An anagram of a string is another string that contains same characters, only the order of characters can be ...
2k views

### 2D Maze solver using recursion in Python

A company I interviewed for sent me a coding problem to solve. The problem was to find a solution to a maze, not necessarily the shortest one. The input would be like so: ...
76 views

### Year with the most living (given a list of births and deaths)

I am trying to find the year most people are alive, given a list of births and deaths. I am not sure my approach is optimal or if am calculating the time complexity correctly Break down: I sort the ...
474 views

### Determine if Array has an Increasing Sequence

I wrote a function in JavaScript that expects an array of integers (negative or positive) and determines if that array has an increasing sequence. For the sake of better time performance I made the ...
174 views

### Non repeating character in Java

Given a string s consisting of lowercase Latin Letters, find the first non repeating character in s. Input: The first line contains T denoting the number of testcases. Then follows ...
126 views

### Star Elements implementation in Java

Given an unsorted array. The task is to find all the star and super star elements in the array. Star are those elements which are strictly greater than all the elements on its right side. Super ...
469 views

### Codility: MaxZeroProduct - complexity issues

My solution scored 100% correctness, but 0% Performance. I just can't figure out how to minimize complexity time. Problem: Write a function: ...
146 views

### Greater on the right side in Java

Given an array of integers, replace every element with the next greatest element (greatest element on the right side) in the array. Since there is no element next to the last element, replace it ...
50 views

### Coordination function

This function started very clean but I had to add requirements: Added a Stopwatch to only update the caller periodically. I guess that responsibility could be ...
2k views

### Count the number of occurences of X's within a range in Java

Given an integer X within the range of 0 to 9, and given two positive integers as upper and lower bounds respectively, find the number of times X occurs as a digit in an integer within the ...
727 views

### Check if array contains contiguous integers with duplicates allowed in Java

Given an array of n integers(duplicates allowed). Print “Yes” if it is a set of contiguous integers else print “No”. INPUT: The first line consists of an integer T i.e. the number of test ...
75 views

### Count total set bits

Im am solving Count total set bits: Find the sum of all bits from numbers 1 to N. Input: The first line of input contains an integer T denoting the number of test cases. The first line ...
811 views

### Reverse a sentence in Java

You are given an array of characters arr that consists of sequences of characters separated by space characters. Each space-delimited sequence of characters defines a word. Implement a function ...
981 views

### Next palindromic number

I wrote a function that takes a number and finds the next palindromic number. Time complexity is currently O(n2), which is really bad. How could one make this function more efficient? ...
1k views

### Removing duplicates from an array

I recently wrote this JavaScript algorithm for removing duplicates from an array as part of a job interview process, but was turned down for the position after submitting the code. I didn't receive ...
85 views

### For every integer in an array, find the nearest greater integer both before and after it

The given code gives correct output but exceeds the time limit and I have no idea how to optimize it. I know it is of $O(n^2)$ complexity but I am not able to get anywhere near to optimizing it. ...
9k views

### JavaScript function to convert decimal number to binary

I was recently asked this in an interview for a front-end position and I came up with something like the code below, which seems to work but is clunky. (...
40 views

### Finding time complexity of my solution to the 'longest palindrome' problem in Python

Here is a short version! ...
309 views

### Pig Latin Script and Runtime

Wrote a basic pig latin script in python where the input is a string and it outputs the pig latin equivalent. I was just wondering what the runtime of this code would be and if there was a way to make ...
108 views

### Compare Strings

You have been given two strings, A and B (of length N each) and Q queries. The strings contain only 0s and/or 1s. For every query, you are given an index i. You have to update the value at ...
2k views

### Program to shorten URL and decode it back to get original URL

TinyURL is a URL shortening service where you enter a URL such as https://leetcode.com/problems/design-tinyurl and it returns a short URL. Design the encode and ...
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 ...
552 views

### Max Increase to Keep City Skyline in Java

In a 2-dimensional array grid, each value grid[i][j] represents the height of a building located there. We are allowed to increase the height of any number of buildings, by any amount (the amounts can ...
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): ...
485 views

### Pancake sort inteview using java

Given an array of integers arr: Write a function flip(arr, k) that reverses the order of the first k elements in the array <...
60 views

### Algorithmic complexity of this algorithm to find all ordered permutations of length X

I have written a recursive function to generate the list of all ordered permutations of length X for a list of chars. For instance: ['a', 'b', 'c', 'd'] with X=2 will give [['a', 'a'], ['a', 'b'], ['...
199 views

### “Tara's Beautiful Permutations” challenge

I'm practising my coding skills using Python to answer medium to difficult problems on sites like HackerRank. Here is the challenge. Given an array of integers, where each number can appear at most ...
509 views

### Finding the majority element in a sequence of integers in $O(n \log n)$

I wrote this piece of code as solution to a problem set that required finding the majority element in a list using divide and conquer in $O(n \log n)$. The majority element is defined as the ...
894 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 ...
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 ...
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,...
790 views

### Merge non overlapping intervals

Merge Intervals Given a set of non-overlapping intervals, insert a new interval into the intervals (merge if necessary). You may assume that the intervals were initially sorted according to their ...
573 views

### Intersection of two lists in Python

I am currently working on an algorithm, which involves finding the intersection of two lists. That is, given the following inputs [1,2,2,1],...
1k views

### Reverse the digits of an Integer

Reverse digits of an integer. Example1: x = 123, return 321 Example2: x = -123, return -321 Return 0 if the result overflows and does not fit in a 32 bit signed integer This is my approach: <...
528 views

### Bottom-up singly linked list merge sort in C++

This is an implementation of a singly linked list merge sort I did on paper during a job interview recently, using a bottom-up approach. The requirement was simply "implement a merge sort for a ...
40 views

### Method that adds edges to a graph until all nodes have the given degree

Exercise 2-3 in Think Complexity: Complexity Science and Computational Modeling by Allen B. Downey asks us to implement a method for a class of undirected graphs: Write a method named ...
7k views

### Finding all integers in an array with odd occurrence

I am doing an interview exercise problem from here. The problem is to find "all numbers that occurred an odd-number of times in an array". Here is my high level psuedo code thinking: Construct a ...
377 views

### Hackerrank “Breaking the Record” solution

I have solved the hacker rank problem listed here. Given a sequence of scores, I need to count the number of times the records for the high and low scores have been broken. Easiest way for me was to ...
Challenge: Given a positive integer which fits in a $32$ bit signed integer, find if it can be expressed as $A^P$ where $P > 1$ and $A > 0$. A and P both should be integers. ...